Bol raz jeden jednobunkový organizmus menom Cecil[^1]. Bolo mu smutno, lebo nebolo nikoho, s kým by sa mohol porozprávať pri jedle, a tak sa Cecil začal deliť, aby mal koho pozvať na svoje párty.

Časom mal Cecil dosť potomkov, a tak sa rozhodol zorganizovať párty. Pozval na ňu všetkých svojich $k$-potomkov. ($1$-potomok Cecila je každé jeho dieťa, $2$-potomok je každé jeho vnúča, atď.)

Postupom času začali aj potomkovia Cecila organizovať párty podobným spôsobom. Každému svojmu $k$-potomkovi pošlú pozvánku na svoju párty. Tá má nasledovnú formu: “Na jeho veľkú párty ťa pozýva tvoj $k$-ty predok, sám magnificentný…”

Cecilovi potomkovia sú ale inteligentní, lebo to bolo v Cecilovych génoch. Je im jasné, že množstvo jedla a kofoly, ktoré sa im na párty ujde, je určené počtom účastníkov párty. Nie vždy sa teda oplatí ísť na párty. Pomôžte im pri rozhodovaní – pre každú pozvánku určite, koľko účastníkov bude na párty ak sa jej všetci pozvaní zúčastnia.

Úloha

Zadaný je zakorenený strom s $n$ vrcholmi. Prichádza vám postupne $m$ otázok. Každá otázka je určená vrcholom $v$ a poradovým číslom predka $k$. Pre každú otázku zistite, koľko $k$-potomkov má $k$-predok vrchola $v$. Ak $k$-predok vrcholu $v$ neexistuje, tak je odpoveď $0$.

$1$-potomok vrcholu $v$ je ľubovoľné jeho dieťa. Pre $k > 1$ je $k$-potomok vrcholu $v$ ľubovoľné dieťa niektorého $(k-1)$-potomka $v$. $1$-predok vrcholu $v$ je otec $v$ ak existuje. Pre $k > 1$ je $k$-predok vrcholu $v$ otec $(k-1)$-predka $v$.

Úlohu je nutné riešiť online – váš program sa nedozvie ďalšiu otázku, kým neodpovie na tú aktuálnu. Za každou odpoveďou preto použite fflush(stdio) alebo cout << flush, aby sa výstup vášho programu hneď odoslal testovaču.

Formát vstupu

Na prvom riadku vstupu je celé číslo $t$ ($1 \leq t \leq 1\,000$) – počet testov. Každý z testov má nasledovný formát:

Prvý riadok testu obsahuje jedno celé číslo $n$ ($1 \leq n \leq 100\,000$) – počet vrcholov stromu. Druhý riadok testu obsahuje $n$ čísel $p_1, p_2, \ldots, p_n$ – $i$-te z nich je číslo priameho predka vrcholu $i$. Ak je vrchol $i$ koreňom stromu, tak $p_i = 0$. (Pre $i$ také, že vrchol $i$ nie je koreňom stromu platí $1 \leq p_i \leq n$.) Môžete predpokladať, že zadaný graf je naozaj strom.

Tretí riadok testu obsahuje jedno celé číslo $m$ ($1 \leq m \leq 100\,000$) – počet otázok. Nasleduje $m$ riadkov, $i$-ty z nich obsahuje dve celé čísla $v_i, k_i$ ($1 \leq v_i, k_i \leq n$) popisujúce otázku.

Súčet $n$ zo všetkých testov nepresiahne $100\,000$, a súčet $m$ zo všetkých testov nepresiahne $150\,000$.

Formát výstupu

Pre každú otázku vypíšte na samostatný riadok jedno celé číslo – počet $k$-potomkov $k$-predka vrcholu $v$.

Príklad

Input:

2
8
4 4 2 0 4 5 5 5
6
1 1 // 1-predok 1 je 4.
    // Jeho 1-potomkovia su 5, 2 a 1.
1 2 // 2-predok 1 neexistuje.
3 1 // 1-predok 3 je 2.
    // Jeho 1-potomok je len 3.
3 2 // 2-predok 3 je 4.
    // Jeho 2-potomkovia su 8, 7, 6 a 3.
3 3 // 3-predok 3 neexistuje.
5 1 // 1-predok 5 je 4.
    // Jeho 1-potomkovia su 5, 2 a 1.
5
3 0 2 5 1
5
4 5
4 1
1 2
1 3
2 1

Output:

3
0
1
4
0
3
0
1
1
0
0

Text uvedený za // je komentár – v skutočných vstupoch sa žiadne komentáre samozrejme nachádzať nebudú. Druhý test má správny formát. Strom v prvom teste vyzerá nasledovne:

1. Možno ste už počuli o jeho pradedovi Bacilovi.↩