给定两棵均有 $n$ 个顶点的树 $T_1$ 和 $T_2$。已知 $T_1$ 中各边的长度，且每条边的长度均为非负整数。

若存在一种为 $T_2$ 的每条边分配长度的方式，使得以下条件成立，则称一棵有 $n$ 个顶点的树 $T$ 是“好的”： * 对于每一对满足 $1 \le i < j \le n$ 的顶点 $i, j$，它们在 $T$ 中的距离与在 $T_2$ 中的距离相等。

你可以对 $T_1$ 执行以下操作：选择 $T_1$ 中的一条边，将其长度替换为任意非负整数。 求使 $T_1$ 变为“好的”所需的最少操作次数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 8600$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 10^6$)。 第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \le p_i \le n$)。 第三行包含 $n-1$ 个整数 $val_2, val_3, \dots, val_n$ ($0 \le val_i \le 10^9$)。 这两行描述了 $T_1$ 中 $n-1$ 条边 $(u, p_u)$，其权重为 $val_u$。 第四行包含 $n-1$ 个整数 $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i \le n$)，描述了 $T_2$ 中 $n-1$ 条边 $(u, p'_u)$。 保证 $\sum n \le 1.1 \cdot 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

样例输入 1

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

样例输出 1

1