WarabiCompany

問題文

warabi君はWarabiCoder(株)の社長です。
この会社にはwarabi君を除いて $N$ 人の社員が在籍し、それぞれ $1,2,...,N$と番号がつけられています。
warabi君以外の社員には必ず1人上司が存在します。社員 $1$ の上司はwarabi君で、社員 $i$ の上司は社員 $P_i(2 \leq i \leq N)$ です。
上司は部下に対して指示できます。また、部下の部下、部下の部下の部下...にも間接的に指示できます。
この時、クエリの数$Q$が与えられるので、以下のクエリにそれぞれ答えてください。

$l_i,r_i$ が与えられます。社員 $(l_i,l_i+1...r_i)$ の全員に指示ができる社員の数を出力してください。

追記 自分自身にも指示できます。

制約

• $2 \leq N \leq 10^5$
• $1 \leq P_i \leq N$
• $i \neq P_i$
• $1 \leq Q \leq 10^5$
• $1 \leq l_i \leq r_i \leq N$
• 入力は全て整数

入力

次の形式で与えられる。

クエリは以下の形式
$l_i r_i$

出力

$Q$ 行出力してください。
$i$ 行目には $query_i$ に対する回答を一行で出力してください。

入力例1

10
1 2 2 3 3 3 1 8 8
3
4 7
1 3
5 7

出力例1

3
2
4

warabi君も社員です。