1485_E. Move and Swap
You are given n - 1 integers a_2, ..., 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?

Input

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

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

The second line of each test case contains n-1 integers v_2, v_3, ..., v_n (1 ≤ v_i ≤ n, v_i ≠ 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, ..., a_n (1 ≤ a_i ≤ 10^9) — the numbers written on the vertices.

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

Output

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

Example

Input


4
14
1 1 1 2 3 4 4 5 5 6 7 8 8
2 3 7 7 6 9 5 9 7 3 6 6 5
6
1 2 2 3 4
32 78 69 5 41
15
1 15 1 10 4 9 11 2 4 1 8 6 10 11
62 13 12 43 39 65 42 86 25 38 19 19 43 62
15
11 2 7 6 9 8 10 1 1 1 5 3 15 2
50 19 30 35 9 45 13 24 8 44 16 26 10 40


Output


14
45
163
123

Note

In the first test case, an optimal solution is to: 

  * move 1: r = 4, b = 2; no swap; 
  * move 2: r = 7, b = 6; swap (after it r = 6, b = 7); 
  * move 3: r = 11, b = 9; no swap. 



The total number of points is |7 - 2| + |6 - 9| + |3 - 9| = 14.

<image>

In the second test case, an optimal solution is to: 

  * move 1: r = 2, b = 2; no swap; 
  * move 2: r = 3, b = 4; no swap; 
  * move 3: r = 5, b = 6; no swap. 



The total number of points is |32 - 32| + |78 - 69| + |5 - 41| = 45.
```python
from collections import deque

T = int(input())

def solve(E, W):
    nodes = {idx: (w, []) for idx, w in weights.items()}
    for u, v in E:
        nodes[u][1].append(v)
        nodes[v][1].append(u)

    layers = []
    visited = set([1])
    parents = {idx: None for idx in weights.keys()}
    Q = deque([1])
    while Q:
        layers.append(list(Q))
        l = len(Q)
        for _ in range(l):
            cur_idx = Q.popleft()
            for v in nodes[cur_idx][1]:
                if v not in visited:
                    Q.append(v)
                    visited.add(v)
                    parents[v] = cur_idx

    dp_b = {idx: 0 for idx in weights.keys()}
    dp_r = {idx: 0 for idx in weights.keys()}
    for l in range(1, len(layers)):
        max_w = max([nodes[idx][0] for idx in layers[l]])
        min_w = min([nodes[idx][0] for idx in layers[l]])
        max_dpp_add, max_dpp_sub = -1e10, -1e10
        for v in layers[l]:
            pv = parents[v]
            max_dpp_add = max(max_dpp_add, max(dp_r[pv], dp_b[pv]) + nodes[v][0])
            max_dpp_sub = max(max_dpp_sub, max(dp_r[pv], dp_b[pv]) - nodes[v][0])
        for u in layers[l]:
            p = parents[u]
            dp_r[u] = max(
                dp_r[p] + max(nodes[u][0] - min_w, max_w - nodes[u][0]),
                dp_b[p] + max(nodes[u][0] - min_w, max_w - nodes[u][0])
            )
            # for v in layers[l]:
            #     pv = parents[v]
            #     dp_b[u] = max(dp_b[u], max(dp_r[pv], dp_b[pv]) + abs(nodes[u][0] - nodes[v][0]))

            dp_b[u] = max(max_dpp_add - nodes[u][0], max_dpp_sub + nodes[u][0])

    # print('layers: {}'.format(layers))
    # print('dp: {}'.format(dp_r))

    return max([dp_r[idx] for idx in layers[-1]])


for _ in range(T):
    n = int(input())
    V = list(map(int, input().split(' ')))
    W = list(map(int, input().split(' ')))
    edges = []
    weights = {1: 0}
    for i in range(n-1):
        edges.append((i+2, V[i]))
    
    for i in range(n-1):
        weights[i+2] = W[i]

    print(solve(edges, weights))

```