Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i.
Let d(x,y) denote the distance between vertex x and y in this tree. Here, the distance between vertex x and y is the number of edges on the shortest path from vertex x to y.
Answer Q queries in order. The i-th query is as follows.

• You are given integers L_i and $R_i. Find \displaystyle\sum_{j = 1}^{N} \min(d(j, L_i), d(j, R_i))$.

Input

The input is given from Standard Input in the following format:
N
A_1 B_1
$\vdots$
A_{N-1} B_{N-1}
Q
L_1 R_1
$\vdots$
L_Q R_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Constraints

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i, B_i, L_i, R_i \leq N$
• The given graph is a tree.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4
6
3

Let us explain the first query.
Since d(1, 4) = 2 and d(1, 1) = 0, we have $\min(d(1, 4), d(1, 1)) = 0$.
Since d(2, 4) = 2 and d(2, 1) = 2, we have $\min(d(2, 4), d(2, 1)) = 2$.
Since d(3, 4) = 1 and d(3, 1) = 3, we have $\min(d(3, 4), d(3, 1)) = 1$.
Since d(4, 4) = 0 and d(4, 1) = 2, we have $\min(d(4, 4), d(4, 1)) = 0$.
Since d(5, 4) = 1 and d(5, 1) = 1, we have $\min(d(5, 4), d(5, 1)) = 1$.
0 + 2 + 1 + 0 + 1 = 4, so you should print 4.

Sample Input 2

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

Sample Output 2

14
16
10
16
14
16
8

见题面 Input 部分

见题面 Output 部分