Problem Description

Chino has n jingle bells, and she plans to decorate them on the Christmas tree one by one.

However,this Christmas tree is strange.This tree has n nodes,numbered from 1 to n.Each node has two value $a_i,b_i$. When Chino puts a jingle bell on node i, she will gain beauty value. Formally, after putting one jingle bell, let S be the set of nodes which contains at least one jingle bell, she will get $b_i\times \sum_{j\notin S} a_j$points.

At the beginning,Chino can only put bells on the root node of the Christmas tree and get 0 points.Then Chino can put jingle bells on any node v satisfying (u,v) ∈ E(G),u ∈ S,v $\notin$ S and get its beauty value. Chino want to make Christmas tree the most beautiful, but she don’t know the maximum beauty value she can get. Can you help her?

Input

The first line contains an integer T (1 ≤ T ≤ 5) denoting the count of testcase.

For each testcase,

The first line contains an integer n (1 ≤ n ≤ 100000) denoting the numbers of nodes and jingle bells.

The second line contains n - 1 integers $f_2,f_3,\cdots,f_n$, and $f_i$ represents the parent of node i is node $f_i$ (1 ≤ $f_i$ < i).

The next n lines each contains 2 integers $a_i,b_i$ (0 < $a_i,b_i$ ≤ 10000), which is for the node value $a_i,b_i$. It is guaranteed that $a_1$ = $b_1$ = 0.

It is guaranteed that $\sum n ≤ 2.1\times 10^5$.

Output

For each testcase, one line with one integer denoting the maximum beauty value.

2
4
1 1 2
0 0
3 1
5 1
4 1
10
1 1 2 2 3 3 6 6 6
0 0
4 1
5000 1
3 1
6 1
200 1
1 1
1 1
1 1
1 1

14
16040

Hint

For the first sample, we can put the jingle bells in the order of 1-2-4-3.