Note the unusual memory limit for this problem.

Given a rooted tree with nodes and edges. The -th edge can be described by , which represents an edge connecting node and node , where node is the parent of node .

There are queries. The -th query contains an integer , asking for the length of the longest simple path starting from node in the graph (forest) formed by the first edges. It is guaranteed that there does not exist such that and , i.e., is the root of a tree in the forest.

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases  (). The description of the test cases follows.

The first line of each test case contains an integer  (), representing the number of nodes in the tree.

The next  lines each contain three integers  (), representing that the parent of node  is , and the -th query is .

It is guaranteed that:
For each test case, the  edges form a rooted tree.
For each test case, for any , there does not exist  such that  and .
The sum of  over all test cases does not exceed .

输出描述:

For each test case, output  integers in one line. The -th integer represents your answer to the -th query.

6
4
3 4 1
2 3 1
1 2 1
4
3 4 3
2 1 2
3 2 3
4
1 2 1
3 4 3
2 3 1
4
2 3 1
2 4 2
1 2 1
2
1 2 1
2
2 1 2

0 0 3
1 1 2
1 1 3
0 1 2
1
1

2
5
1 2 3
1 3 4
3 4 1
1 5 1
15
10 14 10
5 8 5
1 3 1
4 7 10
2 5 2
1 2 1
3 4 1
9 10 9
11 13 11
5 6 1
10 12 9
8 9 1
11 15 11
7 11 1

0 0 2 2
1 1 1 1 2 3 3 2 1 3 2 6 1 6