Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke split into $n$ guys, the $i$th Clarke named $name_i$.
They live in $n$ rooms connected by $n-1$ roads. There is only one path between any two rooms. Now, their landlord is to check the name with a long list. The landlord will check $m$ times, at $i$th time, he wants to know the maximum length of the names which appear on the list $s_i$ on the path between $x_i$ and $y_i$ rooms(including $x_i$ and $y_i$).

Input

The first line contains an integer $T(1 \le T \le 10)$, the number of test cases.
For each test case:
The first line contains an integer $n(1 \le n \le 100000)$.
Then $n$ lines follow, the $i$th line contains a string $name_i$.
Then $n-1$ lines follow, the $i$th line contains an integer $f_{i+1}(1 \le f_{i+1} \le i)$, denoting there is an edge between $i+1$ and $f_{i+1}$.
Then $m$ lines follow, the $i$th line contains two integers $x_i, y_i(1 \le x_i, y_i \le n)$ and a string $s_i$.
Every string is composed by lower letter.
$1 \le |name_i|, |s_i|, \sum_{i=1}^{n} |name_i|, \sum_{i=1}^{m} |s_i| \le 100000$

Output

For each test case, print $m$ lines with the answers.

1
4
a
ab
abc
d
1
2
1
3
1 1 abc
1 1 d
1 3 abc

1
0
3

Hint:
Ask 1: $a$ appears in $abc$, so the answer is $1$.  
Ask 2: There is no one appears in $d$, so the answer is $0$.  
Ask 3: $a$, $ab$ and $abc$ appear in $abc$, so the answer is $3$.