Given a tree with $n$ nodes, where each edge has a weight.

There are $m$ queries. For the $i$-th query, you are given $t_i$ nodes (not necessarily distinct). Consider the union of edges on the simple paths between every pair of these nodes. Find the number of ways to choose two distinct edges from this union such that the two edges have the same weight.

Input

The first line contains an integer $n$.

The next $n-1$ lines each contain two integers $a_i$ and $b_i$, representing an edge between $i+1$ and $a_i$ with weight $b_i$.

The next line contains an integer $m$.

The next $m$ lines each contain $t_i+1$ integers. The first integer is $t_i$, followed by $t_i$ integers representing the set of nodes for that query.

Output

For each query, output a single line containing an integer representing the answer.

Examples

Input 1

5
1 1
2 2
3 2
2 1
3
2 1 4
3 1 2 4
1 2

Output 1

1
1
0

Subtasks

Idea: nzhtl1477, Solution: s_r_f, Code: s_r_f, Data: nzhtl1477

For $100\%$ of the data, $1\le n\le 10^5$, $1\le m\le 10^5$, $1\le a_i\le i-1$, $1\le b_i\le n$, $1\le t_i$, and $t_1+\dots+t_m\le 10^5$.

All values above are integers.