Equivalence

You are given two trees $T_1,T_2$, both with $n$ vertices. The lengths of edges of $T_1$ are given. The length of each edge is non-negative.

A tree $T$ with $n$ vertices is good, if there is a way to assign each edge on $T_2$ with a length which satisfies the following condition:

• For each pair $i,j$ satisfying $1 \leq i < j \leq n$, the distances of $i$ and $j$ on $T$ and $T_2$ are the same.

You can perform the following operation on $T_1$: select an edge on $T_1$ and replace its length with any non-negative integer.

Find the minimum number of operations to make $T_1$ good.

Input

The first line of input contains a single integer $T \: (1 \leq T \leq 8600)$, denoting the number of test cases.

For each test case, the first line contains one integer $n \: (2 \leq n \leq 10^6)$.

The second line contains $n − 1$ integers $p_2,p_3,\dots ,p_n (1 \leq p_i \leq n)$.

The third line contains $n-1$ integers $val_2, val_3, \dots,val_n \: (0 \leq val_i \leq 10^9)$

These two lines denotes $n-1$ edges $(u, p_u)$ with weight $val_u$ on $T_1$.

The fourth line contains $n − 1$ integers $p′_2,p′_3,\dots ,p′_n \: (1 \leq p′_i \leq n)$, denoting $n − 1$ edges $(u,p′_u)$ on $T_2$.

Output

For each test case, the only line contains one integer denoting the answer.

Example

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

1