Given a tree with $n$ nodes, where edges are numbered from $1$ to $n-1$, each edge $i$ has a weight $b_i$. The root of the tree is node $1$.

Two edges $x$ and $y$ are said to have an ancestor relationship if and only if the node with the greater depth among the two endpoints of edge $x$ is an ancestor of the node with the greater depth among the two endpoints of edge $y$.

There are $m$ queries. Each query $i$ provides $t_i$ nodes (which may be identical). Consider the union of edges on the simple paths between every pair of these nodes. Find the number of pairs of distinct edges $(x, y)$ such that $x$ is an ancestor of $y$ and $b_x < b_y$.

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, where 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 4
1 3
3
1 1
2 1 3
3 3 4 5

Output 1

0
1
3

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: nzhtl1477

For $100\%$ of the data, $1\le n\le 10^5$, $1\le m\le 10^6$, $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^6$. All values are integers.