E. Братья по крови возвращаются
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп раздобыл дерево родственных связей. Найденное дерево описывает родственные связи n человек, пронумерованных от 1 до n. Каждый человек в этом дереве имеет не более одного непосредственного предка. Также каждый человек в дереве имеет имя, имена не обязательно уникальные.

Назовем человека с номером a 1-прародителем человека с номером b, если человек с номером a является непосредственным предком человека с номером b.

Назовем человека с номером a k-прародителем (k > 1) человека с номером b, если у человека с номером b есть 1-прародитель, и человек с номером a является (k - 1)-прародителем 1-прародителя человека с номером b.

В найденном дереве родственные связи не образуют циклов. Другими словами не существует человека, который непосредственно или косвенно является собственным прародителем (то есть является x-прародителем самого себя, для некоторого x, x > 0).

Назовем человека с номером a k-сыном человека с номером b, если человек с номером b является k-предком человека с номером a.

Поликарп очень сильно интересуется сколько у кого и каких сыновей. Он записал на листочке m пар чисел vi, ki. Помогите ему для каждой пары vi, ki узнать, сколько существует различных имен, среди всех имен ki-сыновей человека с номером vi.

Входные данные

В первой строке входных данных записано единственное целое число n (1 ≤ n ≤ 105) — количество людей в дереве. В следующих n строках записано описание людей в дереве. В i-той из этих строк записаны через пробел строка si и целое число ri (0 ≤ ri ≤ n), где si — имя человека с номером i, а ri — номер непосредственного предка человека с номером i или 0 если у человека с номером i нет непосредственного предка.

В следующей строке записано единственное целое число m (1 ≤ m ≤ 105) — количество записей Поликарпа. В m следующих строках записаны пары целых чисел через пробел. В i-ой строке записаны числа vi, ki (1 ≤ vi, ki ≤ n).

Гарантируется, что родственные связи не образуют циклов. Имена всех людей непустые строки, состоящие из не более чем 20 строчных латинских букв.

Выходные данные

Выведите m целых чисел, разделенных пробельными символами, — ответы на записи Поликарпа. Ответы для записей выводите в том порядке, в котором записи встречаются во входных данных.

Примеры
Входные данные
6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1
Выходные данные
2
2
0
1
0
Входные данные
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
Выходные данные
1
0
0
0
2
0
0