The land of carrot trees is a magical land tree with $N$ nodes and $N-1$ edges, rooted at node $1$. One day, a lonely carrot decides to ask $Q$ queries of the form n d: the number of unordered pairs of nodes that have a depth between $\mathrm{depth}(n)$ and $\mathrm{depth}(n)+d$ have node $n$ as their lowest common ancestor. Note that these pairs may include the node $n$ itself and the pair may be two of the same node. Also note that this $d$ can be larger than the height of the subtree from $n$. Can you help the poor carrot with these queries?

Note: The lowest common ancestor of nodes $u$ and $v$ is the furthest node from the root that is on the path from $u$ to the root and on the path from $v$ to the root.

Constraints

For all subtasks:

$1\le a_i,b_i\le N$

$1\le n_i\le N$

Subtask 1 [10%]

$1\le N,Q\le 200000$

$d_i=N$

Subtask 2 [20%]

$1\le N,Q\le 2000$

$0\le d_i\le N$

Subtask 3 [70%]

$1\le N,Q\le 200000$

$0\le d_i\le N$

Input Specification

The first line will have $N$, the number of nodes.
The next $N-1$ lines will have two integers, $a_i$ and $b_i$, indicating that there is an edge from $a_i$ to $b_i$.
The next line will have $Q$, the number of queries that follow.
The next $Q$ lines will have two space separated integers, $n_i$ and $d_i$, the $n$ and $d$ values for the $i^{\text{th}}$ query.

Output Specification

The answer to each query, each on a new line.

Sample Input

10
1 2
1 3
4 2
5 2
6 2
7 3
8 3
9 5
10 6
5
1 4
1 3
2 1
2 2
1 2

Sample Output

28
28
7
14
20

Explanation for Sample

For the third query, the $7$ unordered pairs are $(2,2),(2,4),(2,5),(2,6),(4,5),(4,6),(5,6)$.