Polycarpus 掌握了一个家谱。找到的树描述了n个人的家庭关系,编号从1到n。这棵树上的每个人至多有一个直系祖先。另外,树中的每个人都有一个名字,这些名字不一定是唯一的。
如果数字 a 的人是数字 b 的人的直接祖先,我们称数字 a 的人为数字 b 的人的 1-祖先。
如果数字 b 的男子有 1-祖先,并且数字 a 的男子是数字 b 的男子的 1-祖先的 (k - 1)-祖先,我们称数字 a 的男子为数字 b 的男子的 k-祖先 (k > 1)。
在树中,家庭关系不形成循环。换句话说,不存在一个人是他自己的直接或间接祖先(即,他是他自己的 x 祖先,对于某些 x,x > 0)。
如果编号为 b 的男子是编号为 a 的男子的 k 祖先,则我们将编号为 a 的男子称为编号为 b 的男子的 k 儿子。
Polycarpus 对每个人有多少个儿子以及哪些儿子非常感兴趣。他拿了一张纸,写下了m对数字vi,ki。帮助他了解每一对 vi、ki 中编号为 vi 的人的 ki-sons 的所有名字中不同名字的数量。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 105) — 树中的人数。接下来的 n 行包含树中人员的描述。第 i 行包含空格分隔的字符串 si 和整数 ri (0 ≤ ri ≤ n),其中 si 是编号为 i 的人的姓名,ri 是编号为 i 的人的直系祖先的编号,如果编号为 i 的人没有直系祖先,则 ri 是 0。
下一行包含一个整数 m (1 ≤ m ≤ 105) — Polycarpus 的记录数。接下来的 m 行包含空格分隔的整数对。第 i 行包含整数 vi、ki (1 ≤ vi, ki ≤ n)。
保证家庭关系不形成循环。所有人的名字都是非空字符串,由不超过20个小写英文字母组成。
输出
打印 m 个以空格分隔的整数 — Polycarpus 记录的答案。按照记录在输入中出现的顺序打印记录的答案。
示例
输入 #1
6 pasha 0 gerald 1 gerald 1 valera 2 igor 3 olesya 1 5 1 1 1 2 1 3 3 1 6 1
输出 #1
2 2 0 1 0
输入 #2
6 valera 0 valera 1 valera 1 gerald 0 valera 4 kolya 4 7 1 1 1 2 2 1 2 2 4 1 5 1 6 1
输出 #2
1 0 0 0 2 0 0