Королевская династия

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

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

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

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

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

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

В следующей строке содержится число $m$ --- количество вопросов, которое интересует Глеба ($1 \le m \le 10^5$). Далее следует $m$ строк, каждая из которых содержит два целых числа $v$ и $k$ ($1 \le v \le n$, $1 \le k \le 10^9$) --- номер исследоваемого представителя династии и интересущее Глеба число поколений.

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

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