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 performs the following query.

• k v_1 r_1 v_2 r_2 ... v_k r_k: For any vertex $x$, if $x$ is within distance $r_i$ of $v_i$ (i.e., the distance is less than or equal to $r_i$), then $x$ is said to satisfy condition $i$. Among all vertices in the tree, output the number of vertices that satisfy at least one of the $k$ given conditions.

Input

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

The next $N-1$ lines each contain two vertex numbers $u, v$ that an edge connects. ($1 \le u, v \le N$)

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

The next $M$ lines contain queries as described above. Each query, unlike the problem statement, is not given on a single line, but is given 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

Print the result of each query on a separate 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

10
7