Equivalence

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.

Sample Input

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

Sample Output

1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（10）