$N$개의 정점으로 이루어진 트리가 있다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. 간선의 가중치는 모두 $1$이다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

• k v_1 r_1 v_2 r_2 ... v_k r_k: 어떠한 정점 $x$가 $v_i$와 거리 $r_i$ 이내에 있다면 (거리가 $r_i$보다 작거나 같다면), $x$가 $i$번 조건을 만족한다고 하자. 트리에 있는 모든 정점들 중, 쿼리로 주어진 $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$개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다. 각 쿼리는 지문과 다르게 한 줄에 들어오지 않으며, $k + 1$개의 줄로 분리되어 주어진다. 예제 입력을 참고하라. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

쿼리로 주어지는 $k$의 합은 $300000$을 넘지 않는다.

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

10
7