给你一棵有根的树，由 n个顶点组成。树中的顶点编号为 1 至 n ，根顶点为 1 。值 a_i 写在第 i个顶点上。

您可以执行以下任意次数(可能为零)的操作：选择一个顶点 v，该顶点至少有一个子顶点；之后将 a_v 增加 1 ；并将 a_u 减少 1 ，（顶点u是v 的子树中所有顶点( v 本身除外)）。不过，每次操作后，所有顶点上的值都应为非负（即不可通过操作使得某个顶点变成负数）。

换句话说，每次操作选择一个顶点，将该顶点的值+1，其子树上的所有节点都-1，同时操作不可使得有顶点的值变为负数。

您的任务是通过上述操作计算出写入根的最大可能值。

第一行包含一个整数 t ( 1≤t≤10⁴) - 测试用例数。

每个测试用例的第一行包含一个整数 n ( 2≤n≤2⋅10⁵) - 树中的顶点数。

第二行包含 n 个整数 a₁,a₂,…,a_n ( 0≤a_i≤10⁹)。( 0≤a_i≤10⁹) - 写入顶点的初始值。

第三行包含 n−1个整数 p₂,p₃,…,p_n ( 1≤p_i≤n)，其中 p_i是树中第 i个顶点的父节点。顶点 1是树根。

输入的附加限制：所有测试用例的 n之和不超过 2⋅10⁵ 。

在第一个测试案例中，可以进行以下一系列操作：



- 对 v=3 执行操作，则顶点上的值为 [0, 1, 1, 1] ；

- 对 v=1 执行操作，则顶点上的值为 [1, 0, 0, 0] 。