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 ~\operatorname{depth}(n)~ and ~\operatorname{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 200\,000~

~d_i = N~

Subtask 2 [20%]

~1 \le N, Q \le 2\,000~

~0 \le d_i \le N~

Subtask 3 [70%]

~1 \le N, Q \le 200\,000~

~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)~.