Problem Statement

We have a rooted tree with $N$ vertices, numbered $1,2,\dots ,N$.

Vertex $1$ is the root, and the parent of Vertex $i(2\le i\le N)$ is Vertex Pi​.

You are given $Q$ queries. In the $i$-th query $(1\le i\le Q)$, given integers Ui​ and Di​, find the number of vertices $u$ that satisfy all of the following conditions:

• Vertex Ui​ is in the shortest path from $u$ to the root (including the endpoints).
• There are exactly Di​ edges in the shortest path from $u$ to the root.

Constraints

• 2≤N≤2×105
• 1≤Pi​<i
• 1≤Q≤2×105
• 1≤Ui​≤N
• 0≤Di​≤N−1
• All values in input are integers.

Sample Input 1

7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5

Sample Output 1

3
1
0
0

In the $1$-st query, Vertices $4$, $5$, and $7$ satisfy the conditions. In the $2$-nd query, only Vertices $7$ satisfies the conditions. In the $3$-rd and $4$-th queries, no vertice satisfies the conditions.