At the very beginning, Victor has a proposition, then this proposition procudes many propositions. Then every proposition procudes more propositions...... Finally there are $n$ propositions. These propositions can be regarded as a tree whose root is $1$.
We assume that the first proposition, whose number is $1$, belongs to the $0$-th generation, and those propositions produced by the $x$-th generation belong to the $x+1$-th generation. We also assume that all of the propositions in the $x$-th generation are in level $x$. Specially, Victor has discovered that the proposition whose number is $i$ can infer the proposition whose number is $x_i$ and all of the propositions in $x_i$'s subtree, whose levels are not greater than $x_i$'s level + $d_i$.
Notice : $a$ is $b$'s father does not show that either $a$ can infer $b$ or $b$ can infer $a$.
Now please determine the number of such ordered pairs $(i,j)$, that $1\leq i < j\leq n$, the proposition $i$ can infer the proposition $j$, and the proposition $j$ can also infer the proposition $i$.
Input
The first line of the input contains an integer $T$, denoting the number of test cases.
In every test case, there is an integer $n$ in the first line, denoting the number of the propositions.
The second line contains $n-1$ integers, the $i$-th integer $f_{i+1}(f_i < i)$ denotes that the proposition $i+1$ is produced by the proposition $f_{i+1}$.
Then there are $n$ lines, the $i$-th line contains two integers $x_i$ and $d_i$.
$1\leq T\leq 5$.
$2\leq n\leq 100000$.
$0\leq d_i < n$.
Output
Your program should print $T$ lines : the $i$-th of these should contain a single integer, denoting the number of such ordered pairs $(i,j)$.
Sample Input
1
4
1 2 1
2 1
1 0
4 0
2 0
Sample Output
6
Hint
If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
