Задача A. Королевская династия ≡

Условие

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

Один из главных методов исторического анализа династии — изучение количества сыновей некоторого ее представителя. Глеб же намеревается произвести настоящую революцию в исследованиях — он намерен изучать не просто количество сыновей, а количество внуков, правнуков, праправнуков и так далее. Однако, династии могли тянуться несколько десятков поколений, а значит общее число кровных потомков очень велико, так что Глебу стало очень тяжело работать. Поскольку на дворе сейчас XXI век, Глеб решил обратиться за помощью к квалифицированным программистам.

Династия представляет собой множество людей, один из которых называется основателем династии, а любой другой представитель династии U имеет отца V, являющегося представителем династии. При этом U является сыном V, или потомком U через 1 поколение. Потомком U через k+1 поколение называется сын V некоторого потомка U через k поколений.

Глеба интересует информация о том, сколько у некоторого представителя династии V существует потомков через k поколений. Разумеется, Глеба интересует далеко не один такой вопрос.

В первом запросе тестового примера у представителя династии номер 1 есть два потомка во 2 поколении: 3 и 5.

Формат входного файла

В первой строке входного файла содержится одно число n — количество человек в династии, которую исследует Глеб (1 ≤ n ≤ 10⁵), представители династии пронумерованы различными натуральными числами от 1 до n. Далее следуют n чисел, i-е из которых задает номер отца i-го представителя династии, или равно −1, если соответствующий представитель является основателем династии.

Гарантируется, что основатель династии ровно один, и что любой упомянутый представитель династии является потомком основателя династии.

В следующей строке содержится число m — количество вопросов, которое интересует Глеба (1 ≤ m ≤ 10⁵). Далее следует m строк, каждая из которых содержит два целых числа v и k (1 ≤ v ≤ n, 1 ≤ k ≤ 10⁹) — номер исследуемого представителя династии и интересующее Глеба число поколений.

Формат выходного файла

Для каждого вопроса выведите одно число — количество потомков через соответствующее число поколений у заданного представителя династии.

Примеры тестов

5
-1 1 2 1 4
2
1 2
4 7

2
0