Clarke and room

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$).

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$

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