#include <bits/stdc++.h>
using namespace std;
constexpr int N = 6e5 + 10, S = 26;
int T, n, q, G[N][S];
namespace LCT {
	#define ls son[u][0]
	#define rs son[u][1]
	bool check(const array<int, S> &x, const array<int, S> &y) {
		for(int i = 0; i < S; i ++) if((x[i] | y[i]) != y[i]) return false;
		return true;
	}
	int rev[N], son[N][2], fa[N], sz[N], pre[N], suf[N], deg[N], par[N];
	array<int, S> f[N], g[N];
	inline bool isroot(int u) {return son[fa[u]][0] != u && son[fa[u]][1] != u;}
	inline bool type(int u) {return son[fa[u]][1] == u;}
	void up(int u) {
		sz[u] = sz[ls] + sz[rs] + 1;
		for(int i = 0; i < S; i ++) f[u][i] = f[ls][i] | f[rs][i];
		if(~pre[u]) f[u][pre[u]] |= deg[u];
		for(int i = 0; i < S; i ++) g[u][i] = g[ls][i] | g[rs][i];
		if(~suf[u]) g[u][suf[u]] |= deg[u];
	}
	void seta(int u) {
		if(!u) return ;
		swap(ls, rs), swap(f[u], g[u]), swap(pre[u], suf[u]), par[u] = pre[u];
		rev[u] ^= 1;
	}
	void dw(int u) {
		if(rev[u]) seta(ls), seta(rs), rev[u] = 0;
	}
	void rot(int u) {
		int f = fa[u], g = fa[f], k = type(u), w = son[u][!k];
		if(!isroot(f)) son[g][type(f)] = u; fa[u] = g;
		if(w) fa[w] = f; son[f][k] = w;
		son[u][!k] = f, fa[f] = u;
		up(f);
	}
	void pushall(int u) {
		if(!isroot(u)) pushall(fa[u]);
		dw(u);
	}
	void splay(int u) {
		pushall(u);
		while(!isroot(u)) {
			int f = fa[u];
			if(!isroot(f)) rot(type(u) == type(f) ? f : u);
			rot(u);
		}
		up(u);
	}
	int findmin(int u) {
		while(ls) dw(u), u = ls;
		splay(u);
		return u;
	}
	void access(int u) {
		for(int x = 0; u; u = fa[x = u]) {
			splay(u);
			int y = rs; rs = 0, suf[u] = -1;
			if(y) {
				int v = findmin(y);
				pre[v] = -1, up(v);
				deg[u] += 1 << par[v];
			}
			if(x) {
				int v = findmin(x);
				pre[v] = par[v];
				suf[u] = par[v];
				deg[u] -= 1ll << par[v];
				up(v);
				rs = v;
			}
			up(u);
		}
	}
	void link(int u, int v, int w) {
		access(v);
		fa[u] = v, par[u] = w, sz[u] = 1;
		pre[u] = suf[u] = -1;
		deg[v] += 1 << w;
	}
	int find(int u, const array<int, S> &s) {
		while(1) {
			dw(u);
			if(check(g[ls], s)) {
				if(~suf[u] && (s[suf[u]] & deg[u]) == deg[u]) {
					if(!rs) return u;
					u = rs;
				}
				else return u;
			} else {
				u = ls;
			}
		}
	}
	void makeroot(int u) {
		access(u), splay(u), seta(u);
	}
	int kth(int u, int k) {
		dw(u);
		if(k <= sz[ls]) return kth(ls, k);
		else if(k == sz[ls] + 1) return u;
		else return kth(rs, k - sz[ls] - 1);
	}
	#undef ls
	#undef rs
}
using namespace LCT;
int ask(int u, const array<int, S> &s) {
	makeroot(u);
	int v;
	for(; ~u;) {
		splay(u);
		v = find(u, s);
		u = -1;
		for(int i = 0, p = -1; i < S; i ++) if(deg[v] >> i & 1) {
			if(!~p || s[i] >> p & 1) u = G[v][i], p = i;
		}
	}
	return v;
}
int query(int u, int k, string str) {
	array<int, S> s;
	for(int i = 0; i < S; i ++) s[i] = 0;
	for(int i = 0; i < str.size(); i ++) {
		for(int j = i; j < str.size(); j ++) s[str[i] - 'A'] |= 1 << str[j] - 'A';
	}
	int v = ask(u, s);
	access(v), splay(v);
	int ans = kth(v, min(k, sz[v]));
	splay(ans);
	return ans;
}
void dfs(int u, int p) {
	pre[u] = suf[u] = par[u] = -1; sz[u] = 1;
	for(int i = 0; i < S; i ++) if(G[u][i]) {
		int v = G[u][i];
		if(v == p) continue;
		dfs(v, u);
		par[v] = i, fa[v] = u, deg[u] += 1 << i;
	}
}
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	for(cin >> T; T; T --) {
		cin >> n;
		static int cases = 0;
		cout << "Case #" << ++ cases << ": ";
		for(int i = 1; i < n; i ++) {
			int u, v; char w;
			cin >> u >> v >> w;
			w -= 'A';
			G[u][w] = v, G[v][w] = u;
		}
		dfs(1, -1);
		int cnt = n;
		cin >> q;
		for(int i = 0; i < q; i ++) {
			int opt;
			cin >> opt;
			if(opt == 1) {
				int u = ++ cnt, v; char w;
				cin >> v >> w;
				w -= 'A';
				G[u][w] = v, G[v][w] = u;
				link(u, v, w);
			} else {
				int u, k;
				string str;
				cin >> u >> k >> str;
				cout << query(u, k + 1, str) << ' ';
			}
		}
		cout << '\n';
		for(int i = 1; i <= cnt; i ++) {
			for(int j = 0; j < S; j ++) f[i][j] = g[i][j] = G[i][j] = 0;
			son[i][0] = son[i][1] = fa[i] = sz[i] = 0;
			rev[i] = pre[i] = suf[i] = par[i] = deg[i] = 0;
		}
	}
	return 0;
}