宪法法庭将因其工作效率低下（显然）而进行重组。在此之前，法庭将不再受理任何新的待处理法律，直到首席法官（即 1 号法官）对重组前提交给法庭的所有待处理法律作出裁决。他所有的下属，即编号大于 1 的法官，都按照旧的时间表工作：对于每个 $i > 1$，$i$ 号法官在 8:00 上班，并立即从他的收件箱中取出 $c_i$ 件待处理法律（如果收件箱中的法律少于 $c_i$ 件，则全部取出），进行评估，并在当天 16:00 下班时，将所有评估后的法律放入他的发件箱。16:00 之后，法律会被转移给下一位法官：从 $i$ 号法官的发件箱中，法律被移至其上级——$p_i$ 号法官的收件箱中。当然，所有法官的最终上级是首席法官，即 1 号法官。首席法官想知道，所有的待处理法律何时会最终进入他的收件箱。为此，他今天提前上班，并亲自清点了其他法官收件箱中待处理法律的数量。结果发现，$i$ 号法官（$i > 1$）的收件箱中包含 $s_i$ 件待处理法律。请帮助首席法官计算需要多少天，所有的待处理法律才会最终进入他的收件箱，以便他能最终对它们作出裁决。

输入格式

输入包含多个测试用例。第一行包含测试用例的数量 $Z$ ($Z \ge 1$)。接下来是所有测试用例。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 5000$)，表示宪法法庭中法官的数量。下一行包含 $n-1$ 个整数 $s_2, s_3, \dots, s_n$，以空格分隔，其中 $s_i$ ($0 \le s_i \le 10^9$) 表示目前在 $i$ 号法官收件箱中的待处理法律数量。下一行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，以空格分隔，其中 $p_i$ ($1 \le p_i < i$) 表示 $i$ 号法官是 $p_i$ 号法官的下属。最后一行（对于该测试用例）包含 $n-1$ 个整数 $c_2, c_3, \dots, c_n$，以空格分隔，其中 $c_i$ ($1 \le c_i \le 10^9$) 是 $i$ 号法官每天评估的法律数量。

所有测试用例的 $n$ 之和不超过 5000。

输出格式

对于每个测试用例，输出一行，包含一个整数：直到所有待处理法律最终进入首席法官收件箱所需的天数。

样例

输入 1

2
4
10 7 9
1 2 2
5 3 3
4
4 0 5
1 2 3
5 1 2

输出 1

6
7

说明

该图显示了每天早晨的状态。天数用粗体写在上方，法官编号写在左侧。首席法官用圆圈表示，而所有其他法官的收件箱用矩形表示。箭头表示上下级关系。代表 $i$ 号法官收件箱的矩形高度为 $c_i$（标在右侧），宽度足以容纳他收件箱中的所有待处理法律。收件箱中的法律被阴影填充，其数量也写在左上角。$i$ 号法官（$i > 1$）每天评估最多 $c_i$ 件法律——在图形上，这对应于从他的收件箱中“移除”第一列法律，并将剩余的法律“向左移动”。移除的法律（在当天结束时）被移动到上级法官 $p_i$ 的矩形中。

Figure 1. 该图显示了每天早晨的状态。天数用粗体写在上方，法官编号写在左侧。首席法官用圆圈表示，而所有其他法官的收件箱用矩形表示。箭头表示上下级关系。代表 $i$ 号法官收件箱的矩形高度为 $c_i$（标在右侧），宽度足以容纳他收件箱中的所有待处理法律。收件箱中的法律被阴影填充，其数量也写在左上角。$i$ 号法官（$i > 1$）每天评估最多 $c_i$ 件法律——在图形上，这对应于从他的收件箱中“移除”第一列法律，并将剩余的法律“向左移动”。移除的法律（在当天结束时）被移动到上级法官 $p_i$ 的矩形中。