We are given a rooted tree consisting of n vertices numbered from 1 to n. The root of the tree is the vertex 1 and the parent of the vertex v is p_v.
There is a number written on each vertex, initially all numbers are equal to 0. Let's denote the number written on the vertex v as a_v.
For each v, we want a_v to be between l_v and r_v (l_v ≤ a_v ≤ r_v).
In a single operation we do the following:
What's the minimum number of operations needed to achieve our goal?
Input
The first line contains an integer t (1≤ t≤ 1000) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer n (2≤ n≤ 2 · 10^5) — the number of the vertices in the tree.The second line of each test case contains n - 1 integers, p_2, p_3, …, p_n (1 ≤ p_i i), where p_i denotes the parent of the vertex i.The i-th of the following n lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10^9).It is guaranteed that the sum of n over all test cases doesn't exceed 2 · 10^5.
Output
For each test case output the minimum number of operations needed.
Examples
Note
In the first test case, we can achieve the goal with a single operation: choose v = 2 and c = [1, 2], resulting in a_1 = 1, a_2 = 2.In the second test case, we can achieve the goal with two operations: first, choose v = 2 and c = [3, 3], resulting in a_1 = 3, a_2 = 3, a_3 = 0. Then, choose v = 3, c = [2, 7], resulting in a_1 = 5, a_2 = 3, a_3 = 7.