问题描述
克拉克是一名人格分裂患者。某一天，克拉克分裂成了$n$个自己，第$i$个克拉克有一个名字$name_i$。
这$n$个克拉克住在了$n$个房间里，靠$n-1$条双向走廊连接，任意两个房间都能相互到达。现在克拉克的房东来查房，每一次都拿了一条长长的名单。房东一共查了$m$次房，第$i$次查房时，房东需要在$x_i$和$y_i$(包括$x_i$和$y_i$)两个房间路径上所有的房间中，找出最长的出现在名单$s_i$中的克拉克的名字。
由于房东需要查房的次数太多了，所以他把这个问题交给了你，你每一次只需要回答最长的名字的长度。
输入描述
第一行一个整数$T(1 \le T \le 10)$，表示数据的组数。
每组数据第一行是一个整数$n(1 \le n \le 100000)$。
接下来$n$行，每行给出一个字符串$name_i$。
接下来$n-1$行，第$i$行有一个整数$f_{i+1}(1 \le f_{i+1} \le i)$，表示$i+1$与$f_{i+1}$有边相连。
接下来一行为一个整数$m(1 \le m \le 100000)$。
接下来$m$行，每行有两个整数$x_i, y_i(1 \le x_i, y_i \le n)$还有一个字符串$s_i$。
字符串只由$26$个小写字母组成。
$1 \le |name_i|, |s_i|, \sum_{i=1}^{n} |name_i|, \sum_{i=1}^{m} |s_i| \le 100000$
输出描述
每组数据输出$m$行，表示答案。
输入样例
1
4
a
ab
abc
d
1
2
1
3
1 1 abc
1 1 d
1 3 abc
输出样例
1
0
3
Hint
询问1：名单abc中出现了名字a，所以最大长度为1。
询问2：名单d没有人的名字出现，所以最大长度为0。
询问3：名单abc中出现了名字a, ab, abc，所以最大长度为3。
