等效

中文题目为机翻，原题目请参考英文题面

给您两棵树 $T_1,T_2$，都有 $n$ 个顶点。给出了 $T_1$ 的边长。每条边的长度均为非负。

如果有办法给 $T_2$ 上的每条边分配满足以下条件的长度，那么有 $n$ 个顶点的树 $T$ 就是好的：

• 对于满足 $1 \leq i < j \leq n$ 的每一对 $i,j$，$i$ 和 $j$ 在 $T$ 和 $T_2$ 上的距离是相同的。

您可以在 $T_1$ 上执行以下操作：在 $T_1$ 上选择一条边，并用任意非负整数替换它的长度。

找出使 $T_1$ 不变的最少操作次数。

输入

第一行输入包含一个整数 $T \: (1 \leq T \leq 8600)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n \: (2 \leq n \leq 10^6)$ 。

第二行包含 $n - 1$ 个整数 $p_2,p_3,\dots ,p_n (1 \leq p_i \leq n)$ 。

第三行包含 $n-1$ 整数 $val_2, val_3, \dots,val_n \: (0 \leq val_i \leq 10^9)$

这两行表示 $T_1$ 上权重为 $val_u$ 的 $n-1$ 边 $(u,p_u)$。

第四行包含 $n - 1$ 个整数 $p′_2,p′_3,\dots ,p′_n \: (1 \leq p′_i \leq n)$ ，表示 $T_2$ 上的 $n - 1$ 条边 $(u,p′_u)$。

输出

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

示例

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

1