CF208E.Blood Cousins

Polycarpus got hold of a family relationship tree. The tree describes family relationships of n people, numbered 1 through n. Each person in the tree has no more than one parent.

Let's call person a a 1-ancestor of person b, if a is the parent of b.

Let's call person a a k-ancestor (k > 1) of person b, if person b has a 1-ancestor, and a is a (k - 1)-ancestor of b's 1-ancestor.

Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an x-ancestor for himself, for some x, x > 0).

Let's call two people x and y (x ≠ y) p-th cousins (p > 0), if there is person z, who is a p-ancestor of x and a p-ancestor of y.

Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote m pairs of integers v__i, p__i. Help him to calculate the number of p__i-th cousins that person v__i has, for each pair v__i, p__i.

波利卡普斯得到了一棵家族关系树。该树描述了编号为 $1$ 到 $n$ 的 $n$ 个人之间的家族关系，其中每个人至多有一个父辈。

若 $a$ 是 $b$ 的父辈，则称 $a$ 为 $b$ 的 1-祖先。

若 $b$ 存在 1-祖先，且 $a$ 是 $b$ 的 1-祖先的 $(k-1)$-祖先（其中 $k > 1$），则称 $a$ 为 $b$ 的 $k$-祖先。

所给的家族关系树中不存在环。换言之，不存在某个人是其自身的祖先（无论是直接还是间接地）；即，对任意 $x > 0$，不存在某人是自身的 $x$-祖先。

若存在某人 $z$，使得 $z$ 同时是 $x$ 和 $y$（其中 $x \ne y$）的 $p$-祖先（$p > 0$），则称 $x$ 和 $y$ 为 $p$-代堂/表兄弟姐妹（简称为 $p$-代亲）。

波利卡普斯想知道每个人有多少位亲戚、分别属于哪一类。他在一张纸上写下了 $m$ 对整数 $(v_i, p_i)$。请帮助他计算：对每一对 $(v_i, p_i)$，求出人 $v_i$ 所拥有的 $p_i$-代亲的数量。

The first input line contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. The next line contains n space-separated integers _r_1, _r_2, ..., r__n, where r__i (1 ≤ r__i ≤ n) is the number of person i's parent or 0, if person i has no parent. It is guaranteed that family relationships don't form cycles.

The third line contains a single number m (1 ≤ m ≤ 105) — the number of family relationship queries Polycarus has. Next m lines contain pairs of space-separated integers. The i-th line contains numbers v__i, p__i (1 ≤ v__i, p__i ≤ n).

第一行输入包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示家谱树中的人数。
第二行包含 $n$ 个用空格分隔的整数 $r_1, r_2, \dots, r_n$，其中 $r_i$（$1 \leq r_i \leq n$）表示第 $i$ 个人的父节点编号；若第 $i$ 个人没有父节点，则 $r_i = 0$。题目保证家庭关系不构成环。

第三行输入一个整数 $m$（$1 \leq m \leq 10^5$）—— 表示 Polycarpus 提出的家庭关系查询次数。
接下来 $m$ 行，每行包含一对用空格分隔的整数。第 $i$ 行包含两个数 $v_i$ 和 $p_i$（$1 \leq v_i, p_i \leq n$）。

Print m space-separated integers — the answers to Polycarpus' queries. Print the answers to the queries in the order, in which the queries occur in the input.

输出 m 个空格分隔的整数——即 Polycarpus 查询的答案。请按照输入中查询出现的顺序输出答案。