Polycarpus 掌握了家庭关系树。该树描述了 n 个人的家庭关系,编号为 1 到 n。树中的每个人都只有一个父母。
如果 a 是 b 的父代,我们称 a 为 b 的 1-祖先。
如果人 b 有一个 1-祖先,并且 a 是 b 的 1-祖先的 (k - 1)-祖先,我们称人 a 为人 b 的 k-祖先 (k > 1)。
家庭关系不会在找到的树中形成循环。换句话说,没有人直接或间接地是他自己的祖先(即,对于他自己来说,对于某些x,x > 0,他是x祖先)。
如果有一个人 z,他是 x 的 p 祖先和 y 的 p 祖先,我们称两个人 x 和 y (x ≠ y) 为 p 代表兄弟姐妹 (p > 0)。
Polycarpus 想知道每个人有多少个表亲以及它们的种类。他拿了一张纸,写下了m对整数vi,pi。帮助他计算出 vi 的每对 vi、pi 有 pi 个表兄弟姐妹的数量。
输入
第一个输入行包含一个整数 n (1 ≤ n ≤ 105) — 树中的人数。下一行包含 n 个空格分隔的整数 r1, r2, ..., rn,其中 ri (1 ≤ ri ≤ n) 是人 i 的父母的数量,如果人 i 没有父母,则为 0。保证家庭关系不会形成循环。
第三行包含一个数字 m (1 ≤ m ≤ 105) — Polycarus 的家庭关系查询数量。接下来的 m 行包含空格分隔的整数对。第 i 行包含数字 vi、pi (1 ≤ vi, pi ≤ n)。
输出
打印 m 个以空格分隔的整数 — Polycarpus 查询的答案。按查询在输入中出现的顺序打印查询的答案。
示例
输入 #1
6 0 1 1 0 4 4 7 1 1 1 2 2 1 2 2 4 1 5 1 6 1
输出 #1
0 0 1 0 0 1 1