#include <string>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
typedef unsigned long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))

const LL HM = 29;
const unsigned int MOD = 1e9+7;
vector<LL> hashes;
vector<LL> hashesinv;
vector<vector<int> > DA;
vector<int> parent;
vector<char> letters; 

LL inverse(int a)
{
	LL tmp = a;
	LL p = MOD -2;
	LL res = 1;
	while(p)
	{
		if(p&1)
		{
			res *= tmp;
			res %= MOD;
		}
		tmp*=tmp;
		tmp%=MOD;
		p>>=1;
	}
	return res;
}

struct FenwickTree
{
	vector<int> data;
	void init(int n)
	{
		data.resize(n);
	}
	void inc(int idx, int val)
	{
		for(;idx<data.size();idx|=idx+1)
		{
			data[idx]+=val;
			if(data[idx]<0)
				data[idx]+=MOD;
			else if(data[idx]>=MOD)
				data[idx]-=MOD;
		}
	}
	int sum(int r) const
	{
		int ret=0;
		while(r>=0)
		{
			ret+=data[r];
			if(ret>=MOD)
				ret -= MOD;
			r=(r&(r+1))-1;
		}
		return ret;
	}
};

struct HNODE
{
	FenwickTree ft;
	FenwickTree ftrev;
	vector<int> path;
	int heavy;
	int depth;
	int otherend;
	int childcounter;
	int bestchild;
	HNODE()
	{
		depth = childcounter = 0;
		bestchild = otherend = heavy = -1;
	}
};

vector<HNODE> hld;

int LCA(int a, int b)
{
	while(hld[a].heavy!=hld[b].heavy)
	{
		if(hld[hld[a].heavy].depth>=hld[hld[b].heavy].depth)
		{
			if(hld[a].heavy!=a)
				a=hld[a].heavy;
			else
				a=parent[a];
		}
		else 
		{
			swap(a,b);
		}
	}
	return (hld[a].depth>hld[b].depth?b:a);
}

bool isHead(int act)
{
	return hld[act].heavy == act && hld[act].otherend!=-1 && hld[act].otherend!=act;
}

int findPosOnPath(int a, int b, int d)
{
	int t = 0;
	int na = a;
	while(hld[a].depth - hld[na].depth<d)
	{
		if(hld[na].heavy!=na)
			na=hld[na].heavy;
		else
			na=parent[na];
	}
	if(hld[a].depth - hld[na].depth > d)
	{
		assert(isHead(na));
		na = hld[na].path[hld[a].depth - hld[na].depth - d];
	}
	return na;
}

LL calcHashToHead(int a, bool reverse)
{
	const int& h = hld[a].heavy;
	if( h==a || h==-1 )
	{
		assert(0);
		return letters[a]-'a';
	}
	const FenwickTree& ft = reverse ? hld[h].ftrev : hld[h].ft;
	LL res = ft.sum(hld[a].depth-hld[h].depth);
	if(reverse)
	{
		res = (res * hashesinv[hld[hld[h].otherend].depth-hld[a].depth])%MOD;
	}
	return res;
}

LL calcHashToInnerNode(int a, int b, bool reverse)
{
	int h = hld[a].heavy;
	assert(isHead(h));
	assert(h==hld[b].heavy);
	assert(hld[a].depth>=hld[b].depth);
	const FenwickTree& ft = reverse ? hld[h].ftrev : hld[h].ft;
	LL r1 = ft.sum(hld[a].depth-hld[h].depth);
	LL r2 = ft.sum(hld[b].depth-hld[h].depth);
	LL res = (r1-r2+MOD)%MOD;
	if(reverse)
	{
		res = (res * hashesinv[hld[hld[h].otherend].depth-hld[a].depth])%MOD;
	}
	else
	{
		res = (res * hashesinv[hld[b].depth-hld[h].depth])%MOD;
	}
	return res;
}

int dist(int a,int b, int lca)
{
	return hld[a].depth + hld[b].depth - 2 * hld[lca].depth;
}

LL calcHash(int a, int b)
{
	assert(hld[a].depth<=hld[b].depth);
	int lca = LCA(a,b);
	int hlca = hld[lca].heavy;
	int tmp = a;
	LL res1 = 0, res2 = 0;
	while(tmp != hlca)
	{
		LL tres = 0;
		if(hld[hld[tmp].heavy].depth < hld[lca].depth)
		{
			tres = (calcHashToInnerNode(tmp,lca, 0)*hashes[dist(lca,b,lca)])%MOD;
		}
		else
		{
			if(hld[tmp].heavy == tmp)
			{
				tres = ((letters[tmp]-'a')*hashes[dist(parent[tmp],b,lca)])%MOD;
			}	
			else
			{
				tres = (calcHashToHead(tmp, 0)*hashes[dist(hld[tmp].heavy,b,lca)])%MOD;
			}
		}
		res1 += tres;
		if(hld[tmp].heavy!=tmp)
			tmp=hld[tmp].heavy;
		else
			tmp=parent[tmp];
	}

	tmp = b;
	while(tmp != hlca)
	{
		LL tres = 0;
		if(hld[hld[tmp].heavy].depth < hld[lca].depth)
		{
			tres = (calcHashToInnerNode(tmp,lca, 1)*hashes[dist(tmp,b,tmp)])%MOD;
		}
		else
		{
			if(hld[tmp].heavy == tmp)
			{
				tres = ((letters[tmp]-'a')*hashes[dist(tmp,b,tmp)])%MOD;
			}	
			else
			{
				tres = (calcHashToHead(tmp, 1)*hashes[dist(tmp,b,tmp)])%MOD;
			}
		}
		res2 += tres;
		if(hld[tmp].heavy!=tmp)
			tmp=hld[tmp].heavy;
		else
			tmp=parent[tmp];
	}

	return res1 + res2;
}

void update(int pos, char c)
{
	const int& head = hld[pos].heavy;
	if(head == pos)
		return;
	assert(head!=-1);
	FenwickTree& ft = hld[head].ft;
	FenwickTree& ftrev = hld[head].ftrev;
	int p = hld[pos].depth - hld[head].depth;
	LL curr = ft.sum(p) - (p?ft.sum(p-1):0);
	curr = ((hashes[p-1]*(c-'a')%MOD) +MOD - curr) %MOD;
	ft.inc(p,curr);

	curr = ftrev.sum(p) - (p?ftrev.sum(p-1):0);
	int op = hld[hld[head].otherend].depth - hld[pos].depth  ;
	curr = ((hashes[op]*(c-'a')%MOD) +MOD - curr) %MOD;
	ftrev.inc(p,curr);
}

void initDA()
{
	DA.clear();
	const int maxN = 1e5+2;
	DA.resize(maxN);
	vector<bool> pr(maxN,1);
	FOR(i,2,maxN) if (pr[i])
	{
		DA[i].push_back(1);
		int j = 2*i;
		while(j<maxN)
		{
			pr[j]=0;
			DA[j].push_back(j/i);
			j+=i;
		}
	}
}

int main(int argc, char** argv)
{
	initDA();
	int T,N,M,u,v,qtype;
	char z[10];
	scanf("%d",&T);
	assert(0<T && 11>T);
	
	vector<vector<pair<int,char> > > neighboors;
	vector<bool> used;
	vector<int> que;
	int root = 0;
	hashes.clear();
	hashesinv.clear();
	hashes.resize(1e5+2);
	hashesinv.resize(1e5+2);
	hashes[0]=1;
	hashesinv[0]=1;
	FOR(i,1,1e5+2)
	{
		hashes[i]=(hashes[i-1]*HM)%MOD;
		hashesinv[i]=inverse(hashes[i]);
	}
	int qctr = 0;
	int sN= 0, sM=0;
	while(T--)
	{
		scanf("%d",&N);
		assert(1<N && N<=1e5);
		sN+=N;
		neighboors.clear();
		neighboors.resize(N);
		letters.clear();
		letters.resize(N);
		used.clear();
		used.resize(N);
		parent.clear();
		parent.resize(N);
		REP(i,N-1)
		{
			scanf("%d %d %s",&u,&v,z);
			assert(u>0 && u<N+1);
			assert(v>0 && v<N+1);
			assert(u!=v);
			assert(strlen(z)==1);
			assert('a'<=z[0] && 'z'>=z[0]);
			--u;--v;
			neighboors[u].push_back(make_pair(v,z[0]));
			neighboors[v].push_back(make_pair(u,z[0]));
		}
		//build parent & letters
		used[0]=1;
		que.clear();
		que.reserve(N);
		que.push_back(0);
		REP(i,que.size())
		{
			const int& act = que[i];
			REP(j,neighboors[act].size()) if(!used[neighboors[act][j].first])
			{
				que.push_back(neighboors[act][j].first);
				parent[neighboors[act][j].first]=act;
				letters[neighboors[act][j].first]=neighboors[act][j].second;
				used[neighboors[act][j].first]=1;
			}
		}
		assert(que.size()==N);
		//build HLD + Hash
		hld.clear();
		hld.resize(N);
		hld[0].heavy = 0;
		FOR(i,1,N)
		{
			const int& act = que[i];
			const int& par = parent[act];
			hld[act].depth = hld[par].depth + 1;
		}
			
		for(int i = N-1;i>0;--i)
		{
			const int& act = que[i];
			const int& par = parent[act];
			hld[par].childcounter += hld[act].childcounter + 1;
			//setup heavy
			if(hld[par].bestchild==-1 || hld[hld[par].bestchild].childcounter<hld[act].childcounter)
			{
				
				hld[par].bestchild=act;
			}
		}
		FOR(i,1,N)
		{
			const int& act = que[i];
			const int& par = parent[act];
			if(hld[par].bestchild == act)
			{
				hld[act].heavy = hld[par].heavy;
				hld[hld[act].heavy].otherend = act;
			}
			else
			{
				hld[act].heavy = act;
				hld[act].otherend = act;
			}
		}
		REP(act,N) if(isHead(act))
		{//this is a heavy edge
			const int& other = hld[act].otherend;
			int dist = hld[other].depth - hld[act].depth + 1;
			FenwickTree& ft = hld[act].ft;
			FenwickTree& ftrev = hld[act].ftrev;
			ft.init(dist);
			ftrev.init(dist);
			int st = other;
			vector<int>& path = hld[act].path;
			path.reserve(dist);
			while(st!=act)
			{
				update(st,letters[st]);
				path.push_back(st);
				st=parent[st];
			}
			path.push_back(act);
			reverse(path.begin(),path.end());
		}
		scanf("%d",&M);
		assert(1<M && M<=1e5);
		sM+=M;
		REP(Q,M)
		{
			scanf("%d %d %d",&qtype,&u,&v);
			--u,--v;
			switch( qtype )
			{
				case 1:
					{
						++qctr;
						int lca = LCA(u,v);
						int dist = hld[u].depth + hld[v].depth - 2 * hld[lca].depth;
						if(hld[u].depth > hld[v].depth)
							swap(u,v);
						//2nd step calculate hash from the u -> v
						LL lh = calcHash(u,v);
						//3rd try to find some period
						int actd = dist+1;
						int found = dist;
						int candidateD, candidatePos;
						int i=0;
						while(found < actd)
						{
							actd = found;
							while(i < DA[actd].size())
							{
								candidateD = DA[actd][i];
								candidatePos = findPosOnPath(v,u,candidateD);
								
								LL candh = calcHash(candidatePos,v);
								LL lhh = (lh*(hashes[candidateD]-1))%MOD;
								LL chh = (candh*(hashes[dist]-1))%MOD;
								if( lhh == chh)
								{
									found = candidateD;
									break;
								}
								else 
									++i;
							}
						}
						printf("%d\n",found);
						break;
					}
				case 2:
					{
						scanf("%s",z);
						assert(strlen(z)==1);
						if(parent[u]!=v)
						{
							swap(u,v);
						}
						assert(parent[u]==v);
						//update u heavy ft if need
						if(hld[hld[u].heavy].otherend!=-1 && hld[hld[u].heavy].otherend!=hld[u].heavy)
							update(u,z[0]);
						letters[u]=z[0];
						break;
					}
				default:
					{
						assert(0);
					}
			}
		}
	}
	return 0;
}