Problem Description

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\le i< j\le 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\le T\le 8600$), denoting the number of test cases.

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

The second line contains $n-1$ integers $p_2, p_3,\cdots, p_n$ ($1 \le p_i \le n$).

The third line contains $n-1$ integers $val_2,val_3,\cdots, val_n$ ($0 \le val_i \le 10^9$).

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

The fourth line contains $n-1$ integers $p'_2, p'_3,\cdots, p'_n$ ($1 \le p'_i \le n$), denoting $n-1$ edges $(u,p'_u)$ on $T_2$.

It is guaranteed that $\sum n\le 1.1\cdot 10^6$.

Output

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

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

1