You are given $n - 1$ integers $a_2, \dots, a_n$ and a tree with $n$ vertices rooted at vertex $1$. The leaves are all at the same distance $d$ from the root.

Recall that a tree is a connected undirected graph without cycles. The distance between two vertices is the number of edges on the simple path between them. All non-root vertices with degree $1$ are leaves. If vertices $s$ and $f$ are connected by an edge and the distance of $f$ from the root is greater than the distance of $s$ from the root, then $f$ is called a child of $s$.

Initially, there are a red coin and a blue coin on the vertex $1$. Let $r$ be the vertex where the red coin is and let $b$ be the vertex where the blue coin is. You should make $d$ moves. A move consists of three steps:

• Move the red coin to any child of $r$.
• Move the blue coin to any vertex $b'$ such that $dist(1, b') = dist(1, b) + 1$. Here $dist(x, y)$ indicates the length of the simple path between $x$ and $y$. Note that $b$ and $b'$ are not necessarily connected by an edge.
• You can optionally swap the two coins (or skip this step).

Note that $r$ and $b$ can be equal at any time, and there is no number written on the root.

After each move, you gain $|a_r - a_b|$ points. What's the maximum number of points you can gain after $d$ moves?

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of vertices in the tree.

The second line of each test case contains $n-1$ integers $v_2, v_3, \dots, v_n$ ($1 \leq v_i \leq n$, $v_i \neq i$)  — the $i$-th of them indicates that there is an edge between vertices $i$ and $v_i$. It is guaranteed, that these edges form a tree.

The third line of each test case contains $n-1$ integers $a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the numbers written on the vertices.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

For each test case, print a single integer: the maximum number of points you can gain after $d$ moves.