Zayin 想要和他的朋友们一起去动物园。但是他自己的车坐不下这么多人。所以，他打算使用自己的巴士。

巴士上有 $n$ 个座位（编号从 $1$ 到 $n$）和 $n-1$ 条通道。每条通道连接两个座位。一个人可以通过一条或多条通道从一个座位走到另一个座位。巴士的入口连接着座位 $1$。共有 $n$ 个人，编号从 $1$ 到 $n$。他们按从第 $1$ 个人到第 $n$ 个人的顺序上车。Zayin 需要为这 $n$ 个人安排座位。每个人都会沿着最短路径走到自己的座位，然后立即开始入座。第 $i$ 个人在第 $i$ 秒上车并到达座位 $1$。在每一秒内，每个人可以通过一条通道。第 $i$ 个人需要 $a[i]$ 秒来入座。在此之后，没有人能再到达该座位。（详情请参阅说明。）

如果每个人都到达了自己的座位并顺利入座，Zayin 就可以启动他的巴士。Zayin 需要找到一种安排方式，使得他能尽快启动巴士。Zayin 想知道完成这一过程所需的最短时间。

说明

假设 $a[1] = 1$，且他的目的地是座位 $1$。他在第 $1$ 秒上车，并将在第 $2$ 秒完成入座。其他人仍然可以在第 $2$ 秒上车，但第 $3$ 秒是不允许的，因为座位 $1$ 已经被占用了。

如果他的目的地是座位 $2$，他将在第 $2$ 秒到达，并在第 $3$ 秒完成入座。那么从第 $4$ 秒开始，没有人能到达座位 $2$。

输入格式

第一行包含一个整数 $T(1 \le T \le 15)$，表示测试用例的数量。 每个测试用例以一个正整数 $n(1 \le n \le 10^5)$ 开始。 下一行包含 $n-1$ 个整数。第 $i$ 个数是 $f[i]$，表示在座位 $f[i]$ 和座位 $i+1$ 之间有一条通道。保证 $1 \le f[i] \le i$。 下一行包含 $n$ 个整数。第 $i$ 个数是 $a[i]$ $(1 \le a[i] \le 10^8)$。

输出格式

对于每个测试用例，输出一行，表示最短可能时间。

样例

输入 1

2
3
1 1
1 3 2
3
1 2
1 3 2

输出 1

6
6