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

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.

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.