不easy啊。。

一个小错误让我wa死了。找了一个晚上，怎么都找不到

最后是对拍代码找到的错误。发现当步数比較小的时候答案就是对的，比較大的时候就不正确了

想到一定是什么地方越界了。。

。

power[i] = (i64)(power[i - 1] * 26) % mod;

就是这行。。

。

改成  power[i] = ((i64)power[i - 1] * 26) % mod;

就过了。。。

这道题总的来说就是很综合，什么方面都涉及一点，核心部分还是把树转化成序列之后二分边界+RMQ,用dfn来确定边界的这种方法很好，很有意思

事实上另一种方法，就是先从u节点往下走一步。然后在trie里面找，这个时候能够直接确定位置。由于在trie中已经是有序的了

两种都能够，第一种相对来说好实现一点

（hdu如今怎么不会爆栈了。

。）

//#pragma comment(linker, "/STACK:102400000,102400000")

#include<iostream>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<stack>

#include<string>

#include<map>

#include<set>

#include<cmath>

#include<cassert>

#include<cstring>

#include<iomanip>

using namespace std;

#ifdef _WIN32

typedef __int64 i64;

#define out64 "%I64d\n"

#define in64 "%I64d"

#else

typedef long long i64;

#define out64 "%lld\n"

#define in64 "%lld"

#endif

/************ for topcoder by zz1215 *******************/

#define foreach(c,itr)  for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)

#define FF(i,a)         for( int i = 0 ; i < (a) ; i ++)

#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)

#define S64(a)          scanf(in64,&a)

#define SS(a)           scanf("%d",&a)

#define LL(a)           ((a)<<1)

#define RR(a)           (((a)<<1)+1)

#define pb              push_back

#define pf              push_front

#define X               first

#define Y               second

#define CL(Q)           while(!Q.empty())Q.pop()

#define MM(name,what)   memset(name,what,sizeof(name))

#define MC(a,b)		memcpy(a,b,sizeof(b))

#define MAX(a,b)        ((a)>(b)?(a):(b))

#define MIN(a,b)        ((a)<(b)?(a):(b))

#define read            freopen("out.txt","r",stdin)

#define write           freopen("out1.txt","w",stdout)

const int inf = 0x3f3f3f3f;

const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;

const double oo = 10e9;

const double eps = 10e-9;

const double pi = acos(-1.0);

const int mod = 1000000007;

const int maxn = 100111;

struct Node

{

	int now;

	int to;

	int c;

};

struct Trie

{

	int to[26];

	int rank;

}zx[maxn];

int head = 0;

int use;

int get()

{

	use++;

	MM(zx[use].to, -1);

	zx[use].rank = 0;

	return use;

}

int T;

int n, m;

vector<Node>g[maxn];

vector<int>level[maxn];

int dep[maxn];

int dfn[maxn];

int dfv[maxn];

int df;

int power[maxn];

int vis[maxn];

int t[maxn];

int pos[maxn];

int pmod[maxn];

int rankmod[maxn];

int rk;

int c[maxn];

int dfnpos[maxn];

int es[maxn][2];

vector<int>ary;

int st[maxn][20];

int pow2[20];

int lg2[maxn];

void dfs(int now=1,int step=0)

{

	vis[now] = true;

	int to;

	dfn[now] = df;

	dfv[df] = now;

	df++;

	dep[now] = step;

	for (int i = 0; i <(int) g[now].size(); i++)

	{

		to = g[now][i].to;

		if (!vis[to])

		{

			t[to] = now;

			c[to] = g[now][i].c;

			dfs(to,step+1);

		}

	}

}

void make_trie()

{

	use = -1;

	get();

	int trie = head;

	int now = 1;

	pos[now] = trie;

	int to,temp;

	pmod[0] = 0;

	for (int i = 2; i < df; i++)

	{

		to = dfv[i];

		now = t[to];

		trie = pos[now];

		if (zx[trie].to[c[to]] == -1)

		{

			temp = get();

			zx[trie].to[c[to]] = temp;

			pmod[temp] = ((i64)pmod[trie] * 26 + c[to]) % mod;

		}

		pos[to] = zx[trie].to[c[to]];

	}

}

void make_rank(int now = head)

{

	zx[now].rank = rk++;

	for (int i = 0; i < 26; i++)

	{

		if (zx[now].to[i] != -1)

		{

			make_rank(zx[now].to[i]);

		}

	}

}

void sparsetable()

{

	for (int i = 1; i <= n; i++)

	{

		st[i][0] = zx[pos[dfv[ary[i]]]].rank;

	}

	for (int j = 1; j <= lg2[n]; j++)

	{

		for (int i = 1; i <= n; i++)

		{

			if (i + pow2[j - 1] <= n)

			{

				st[i][j] = max(st[i][j - 1], st[i + pow2[j - 1]][j - 1]);

			}

			else

			{

				st[i][j] = st[i][j - 1];

			}

		}

	}

}

int rmq(int l,int r)

{

	return max(st[l][lg2[r - l]], st[r - pow2[lg2[r - l]]][lg2[r - l]]);

}

int find(int x, int step)

{

	int low = dfn[x];

	int up;

	int temp = dfnpos[dfn[x]] + 1;

	step += dep[x];

	int l, r;

	if (temp < es[dep[x]][1])

	{

		up = ary[temp];

	}

	else

	{

		up = inf;

	}

	l = upper_bound (ary.begin() + es[step][0], ary.begin() + es[step][1], low ) - ary.begin();

	r = upper_bound (ary.begin() + es[step][0], ary.begin() + es[step][1], up ) - ary.begin();

	if (l == r)

	{

		return -1;

	}

	int mrank = rmq(l, r);

	int xrank = zx[pos[x]].rank;

	return (((i64)rankmod[mrank] - ((i64)rankmod[xrank] * (i64)power[step - dep[x]])%mod)+mod)%mod;

}

void start()

{

	for (int i = 0; i <= n; i++)

	{

		vis[i] = false;

	}

	t[1] = -1;

	df = 1;

	dfs();

	for (int i = 1; i <= n; i++)

	{

		level[dep[i]].push_back(dfn[i]);

	}

	for (int i = 1; i <= n; i++)

	{

		sort(level[i].begin(), level[i].end());

	}

	ary.clear();

	ary.push_back(0);

	for (int i = 0; i <= n; i++)

	{

		es[i][0] = ary.size();

		for (int j = 0; j < (int)level[i].size(); j++)

		{

			ary.push_back(level[i][j]);

		}

		es[i][1] = ary.size();

	}

	for (int i = 1; i <= n; i++)

	{

		dfnpos[ary[i]] = i;

	}

	make_trie();

	rk = 0;

	make_rank();

	for (int i = 0; i <= use; i++)

	{

		rankmod[zx[i].rank] = pmod[i];

	}

	sparsetable();

}

void destroy()

{

	for (int i = 0; i <= n; i++)

	{

		g[i].clear();

		level[i].clear();

	}

}

int main()

{

	//read;

	//write;

	power[0] = 1;

	for (int i = 1; i < maxn; i++)

	{

		power[i] = ((i64)power[i - 1] * 26) % mod;

	}

	pow2[0] = 1;

	lg2[1] = 0;

	for (int i = 1; i < 20; i++)

	{

		pow2[i] = pow2[i - 1] * 2;

		if(pow2[i]<maxn)

		lg2[pow2[i]] = i;

	}

	for (int i = 3; i < maxn; i++)

	{

		if (!lg2[i])

		{

			lg2[i] = lg2[i - 1];

		}

	}

	cin >> T;

	while (T--)

	{

		cin >> n;

		int x, y;

		char z;

		Node node;

		for (int i = 1; i <= n - 1; i++)

		{

			//cin >> x >> y >> z;

			scanf("%d%d %c", &x, &y, &z);

			node.now = x;

			node.to = y;

			node.c = z - 'a';

			g[node.now].push_back(node);

			swap(node.now, node.to);

			g[node.now].push_back(node);

		}

		start();

		cin >> m;

		for (int i = 1; i <= m; i++)

		{

		//	cin >> x >> y;

			scanf("%d%d", &x, &y);

			if (y == 0)

			{

				printf("0\n");

				continue;

			}

			int ans = find(x, y);

			if (ans == -1)

			{

			//	cout << "IMPOSSIBLE" << endl;

				printf("IMPOSSIBLE\n");

			}

			else

			{

			//	cout << ans << endl;

				printf("%d\n",ans);

			}

		}

		destroy();

	}

	return 0;

}