Đếm Hậu Duệ Theo Độ Sâu

Có một cây gốc gồm $n$ đỉnh, đánh số từ $1$ đến $n$, với gốc là đỉnh $1$. Với mỗi đỉnh $v$ từ $2$ đến $n$, cha trực tiếp của nó là $p_v$.

Độ sâu của một đỉnh là số cạnh trên đường từ gốc $1$ đến đỉnh đó; do đó gốc có độ sâu $0$.

Mỗi truy vấn cho hai số u,d. Hãy đếm số đỉnh $x$ thỏa đồng thời:

• $x$ thuộc cây con gốc $u$, kể cả trường hợp $x=u$;
• độ sâu tuyệt đối của $x$ bằng đúng $d$.

Lưu ý $d$ là độ sâu tính từ gốc $1$, không phải khoảng cách từ $u$.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng tiếp theo chứa $n-1$ số $p_2,p_3,\dots ,p_n$.
• Dòng tiếp theo chứa số nguyên $q$.
• Mỗi dòng trong $q$ dòng cuối chứa hai số nguyên $u,d$.

Output

• In $q$ dòng; dòng thứ $i$ là số đỉnh thỏa truy vấn thứ $i$.

Constraints

• $2\le n\le 2\cdot 10^5$.
• $1\le p_v<v$ với mọi $2\le v\le n$.
• $1\le q\le 2\cdot 10^5$.
• $1\le u\le n$.
• $0\le d\le n-1$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 3000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

9
1 1 2 2 3 3 6 6
6
1 2
2 2
3 3
6 2
6 1
8 3

4
2
2
1
0
1