You are given a rooted tree with ( n ) vertices. The vertices in the tree are numbered from 1 to ( n ), and the root is the vertex 1. The value ( a_i ) is written at the ( i )-th vertex.

You can perform the following operation any number of times (possibly zero):

1. Choose a vertex ( v ) that has at least one child.
2. Increase ( a_v ) by 1.
3. Decrease ( a_u ) by 1 for all vertices ( u ) that are in the subtree of ( v ) (except ( v ) itself).

After each operation, ensure that all vertex values are non-negative.

Your task is to calculate the maximum possible value at the root using the aforementioned operations.

Input

• The first line contains a single integer ( t ) (( 1 \leq t \leq 10^4 )) — the number of test cases.
• The first line of each test case contains a single integer ( n ) (( 2 \leq n \leq 2 \cdot 10^5 )) — the number of vertices in the tree.
• The second line contains ( n ) integers ( a_1, a_2, \ldots, a_n ) (( 0 \leq a_i \leq 10^9 )) — the initial values written at vertices.
• The third line contains ( n-1 ) integers ( p_2, p_3, \ldots, p_n ) (( 1 \leq p_i \leq n )), where ( p_i ) is the parent of the ( i )-th vertex in the tree. Vertex 1 is the root.

Additional Constraint

The sum of ( n ) over all test cases does not exceed ( 2 \cdot 10^5 ).

Output

For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.

Example

Input

3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2

Output

1
3
6