Cho một cây với ~n~ đỉnh được đánh số thứ tự từ ~1~ đến ~n~. Đỉnh ~1~ được gọi là gốc, đỉnh cha của đỉnh ~i~ là các đỉnh ~p_i, 2 \le i \le n~.

Bạn được cung cấp ~Q~ truy vấn. Với truy vấn thứ ~i~ cho các số nguyên ~U_i~ và ~D_i~, hãy tìm số đỉnh trong ~u~ thỏa mãn tất cả các điều kiện sau:

• Đỉnh ~U_i~ nằm trên đường đi ngắn nhất từ \(​​u\) đến gốc (kể cả các điểm cuối).

• Có đúng chính xác ~D_i~ cạnh trên đường đi ngắn nhất từ ~u~ đến gốc.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~2 \le n \le 2.10^5~.

Dòng thứ hai chứa ~n-1~ các số nguyên ~p_i~ là các đỉnh cha của các đỉnh thứ ~i~.

Dòng thứ ba chứa số nguyên ~Q~ thỏa ~1 \le Q \le 2.10^5~ là số truy vấn.

~Q~ dòng tiếp theo chứa cặp ~U_i, D_i~ thỏa ~1 \le U_i \le N; 0 \le D_i \le N-1~.

Tất cả đều là số nguyên có giá trị nhỏ hơn ~10^9~.

Output

In ra ~Q~ kết quả của truy vấn, mỗi kết quả in trên một dòng.

Samples

Sample Input 1

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

Sample Output 1

3
1
0
0

Note

Ở truy vấn thứ nhất, các đỉnh ~4, 5, 7~ thỏa mãn điều kiện.

Ở truy vấn thứ hai, chỉ có đỉnh ~7~ thỏa mãn điều kiện.

Ở truy vấn thứ ba và thứ tư không có đỉnh nào thỏa mãn điều kiện.

Ref atcoder