题目描述

波利卡普得到了一个家族关系树。这个树描述了 $n$ 个人的家族关系，编号从 $1$ 到 $n$。树中的每个人最多有一个父母。

如果 $a$ 是 $b$ 的父母，我们称 $a$ 为 $b$ 的 $1$-祖先。

如果 $b$ 有一个 $1$-祖先，并且 $a$ 是 $b$ 的 $1$-祖先的 $(k-1)$ -祖先的，我们称 $a$ 为 $b$ 的 $k$-祖先。

家族关系在找到的树中不形成循环。换句话说，没有人是自己的祖先，无论是直接还是间接的（即，没有人是自己某个 x-祖先）。

如果存在一个人 $z$，他是 $x$ 的 $p$-祖先和 $y$ 的 $p$-祖先 ，我们称两个人 $x$ 和 $y$ 为 ($x$ ≠ $y$) $p$-表亲 ($p$ > 0)。

波利卡普想知道每个人有多少表亲以及他们的种类。他拿了一张纸，写下了 $m$ 对整数 $v_i$，$p_i$。帮助他计算每对 $v_i$，$p_i$ 中，$v_i$ 有多少 $p_i$-表亲。

输入格式

第一行输入包含一个整数 $n$ — 树中人的数量。下一行包含 $n$ 个用空格分隔的整数 $r_1,r_2,...,r_n$，其中 $r_i$ ($1 \le r_i \le n$) 是第 $i$ 个人的父母编号，如果第 $i$ 个人没有父母，则为 $0$。可以保证家族关系不形成循环。

第三行包含一个数字 $m$ — 波利卡普的家族关系查询的数量。接下来的 $m$ 行包含一对用空格分隔的整数。第 $i$ 行包含数字 $v_i$，$p_i$ ($1 \le v_i,p_i \le n$)。

输出格式

输出 $m$ 个用空格分隔的整数 — 波利卡普查询的答案。按照输入中查询出现的顺序输出答案。

6
0 1 1 0 4 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

0 0 1 0 0 1 1 

样例分析

顶点 $2$ 的 $1$-表亲是顶点 $2$，顶点 $5$ 的 $1$-表亲是顶点 $6$。

数据范围与提示

对于 $100\%$ 的数据，$1\le n \le 10^5$，$1 \le m \le 10^5$。