There is a tree (an undirected connected graph without cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$.

Write a program that performs the following queries:

• $u$ $v$ : For a vertex $x$ ($1 \le x \le N$), output the maximum value of $\operatorname{dist}(x, u) + \operatorname{dist}(x, v)$. ($1 \le u, v \le N$)

Here, $\operatorname{dist}(x, y)$ is defined as the number of edges on the shortest path from vertex $x$ to vertex $y$. For all vertices $x$ in the tree, $\operatorname{dist}(x, x) = 0$.

Input

The first line contains the number of vertices $N$ in the tree. ($2 \le N \le 300000$)

The next $(N-1)$ lines provide information about the tree. The $i$-th line contains two vertex numbers connected by the $i$-th edge, separated by a space.

The next line contains the number of queries $Q$. ($2 \le Q \le 300000$)

The following $Q$ lines each contain the information for a query.

Output

Output the answers to the $Q$ queries in order, each on a new line.

Examples

Input 1

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

Output 1

6
5
5