問題文

$N$ 頂点の根付き木があり、頂点は $1, 2, \\dots, N$ と番号付けられています。

頂点 $1$ が根であり、頂点 $i \\, (2 \\leq i \\leq N)$ の親は $P_i$ です。

$Q$ 個のクエリが与えられます。$i \\, (1 \\leq i \\leq Q)$ 番目のクエリでは、整数 $U_i, D_i$ が与えられるので、次の条件を全て満たす頂点 $u$ の個数を求めてください。

• $u$ から根への最短パス上（端点も含む）に頂点 $U_i$ が存在する。
• $u$ から根への最短パスに含まれる辺の数がちょうど $D_i$ である。

制約

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq P_i < i$
• $1 \\leq Q \\leq 2 \\times 10^5$
• $1 \\leq U_i \\leq N$
• $0 \\leq D_i \\leq N - 1$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $P_2$ $P_3$ $\\ldots$ $P_N$ $Q$ $U_1$ $D_1$ $U_2$ $D_2$ $\\vdots$ $U_Q$ $D_Q$

出力

$Q$ 行出力せよ。 $i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。

入力例 1

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

出力例 1

3
1
0
0

$1$ 番目のクエリでは、頂点 $4, 5, 7$ が条件を満たします。 $2$ 番目のクエリでは、頂点 $7$ のみが条件を満たします。 $3$ 番目、$4$ 番目のクエリでは、条件を満たす頂点は存在しません。