$N$ 個の頂点からなる木がある。頂点には $1$ から $N$ までの番号が付けられている。辺の重みはすべて $1$ である。

以下のクエリを実行するプログラムを作成せよ。

• $k \; v_1 \; r_1 \; v_2 \; r_2 \; \dots \; v_k \; r_k$: ある頂点 $x$ が $v_i$ との距離 $r_i$ 以内にあるとき（距離が $r_i$ 以下であるとき）、$x$ は $i$ 番目の条件を満たすとする。木のすべての頂点のうち、クエリで与えられた $k$ 個の条件のうち $k-1$ 個以上の条件を満たす頂点の個数を出力せよ。

入力

最初の行に整数 $N$ が与えられる。（$1 \le N \le 100{,}000$）

続く $N-1$ 行には、各辺が結ぶ二つの頂点番号 $u, v$ が与えられる。（$1 \le u, v \le N$）

次の行に整数 $M$ が与えられる。（$1 \le M \le 300{,}000$）

続く $M$ 行には、上で説明したものと同じクエリが与えられる。各クエリは問題文とは異なり 1 行ではなく、$k+1$ 行に分かれて与えられる。入出力例を参照せよ。（$1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$）

クエリで与えられる $k$ の総和は $300000$ を超えない。

出力

クエリの結果を 1 行に 1 つずつ出力せよ。

入出力例

入力例 1

10
1 3
6 4
9 8
1 8
3 4
2 8
10 3
4 5
8 7
2
3
8 1
3 1
3 2
2
7 3
6 0

出力例 1

5
7