왕조

글렙은 역사를 아주 좋아한다. 특정 왕조의 역사를 조사하라고 하면 매우 기뻐한다. 글렙은 혈통의 순수함을 엄격히 따지기 때문에, 왕조를 분석할 때 창시자의 부계 혈통 직계 남성만 고려한다.

왕조를 역사적으로 분석하는 주요 방법 중 하나는 어떤 인물의 아들 수를 세는 것이다. 글렙은 연구에 혁명을 일으키려 한다. 단순히 아들 수가 아니라 손자, 증손자, 고손자 등의 수를 세려는 것이다. 그러나 왕조는 수십 세대에 걸쳐 이어질 수 있어 혈통 직계 후손의 총수가 매우 많아지므로, 글렙이 작업하기가 매우 어려워졌다. 지금이 21세기이니 글렙은 실력 있는 프로그래머에게 도움을 청하기로 했다.

왕조는 사람들의 집합이다. 그중 한 명을 왕조의 창시자라 하고, 나머지 왕조 구성원 $U$에게는 왕조 구성원인 아버지 $V$가 있다. 이때 $U$는 $V$의 아들이며, $U$의 1세대 후손이다. 어떤 $U$의 $k$세대 후손의 아들 $V$를 $U$의 $k+1$세대 후손이라 한다.

글렙은 어떤 왕조 구성원 $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$). $v$는 조사할 왕조 구성원의 번호이고 $k$는 글렙이 궁금해하는 세대 수이다.

각 질문마다 주어진 왕조 구성원의 해당 세대 후손 수를 한 줄에 하나씩 출력한다.

첫 번째 질문에서 1번 왕조 구성원에게는 2세대 후손이 3번과 5번, 두 명 있다.