There is a tree consisting of $N$ vertices. The vertices are numbered from $1$ to $N$. All edges have weight $1$.

Write a program that processes the following query.

• k v_1 r_1 v_2 r_2 ... v_k r_k: For a vertex $x$, if $x$ is within distance $r_i$ from $v_i$ (i.e., the distance is less than or equal to $r_i$), we say that $x$ satisfies the $i$-th condition. Among all vertices in the tree, count the number of vertices that satisfy at least $k-1$ of the $k$ conditions given in the query.

Input

The first line contains an integer $N$. ($1 \le N \le 100{,}000$)

The next $N-1$ lines each contain two integers $u, v$ representing an edge connecting the two vertices. ($1 \le u, v \le N$)

The next line contains an integer $M$. ($1 \le M \le 300{,}000$)

The next $M$ lines contain the queries as described above. Unlike the description in the problem statement, each query is not given on a single line; it is split into $k+1$ lines. Refer to the sample input. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

The sum of $k$ over all queries does not exceed $300000$.

Output

For each query, output the result on its own line.

Examples

Input 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

Output 1

5
7