E. Братья по крови
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
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).

Назовем двух людей x и y (x ≠ y) p-юродными братьями (p > 0), если существует человек z, который является p-прародителем x и p-прародителем y.

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

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

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

В третьей строке записано единственное целое число m (1 ≤ m ≤ 105) — количество записей Поликарпа. В m следующих строках записаны пары целых чисел через пробел. В i-ой строке записаны числа vi, pi (1 ≤ vi, pi ≤ 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