There is a tree (a connected undirected graph with no 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 query.

• $u$ $v$: For vertex $x$ ($1 \le x \le N$), print the maximum value of $\operatorname{dist}(x, u) \times \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 any vertex $x$, $\operatorname{dist}(x, x) = 0$.

Input

The first line of input contains $N$, denoting the number of vertices of the tree. ($2 \le N \le 300\,000$)

The following $(N-1)$ lines contain the information of the tree. The $i$-th of them contains two space-separated integers denoting the two vertices connected by edge $i$.

The next line contains $Q$, denoting the number of queries. ($2 \le Q \le 300\,000$)

Each of the following $Q$ lines contains the information for each query in the same format as written in the problem statement.

Output

Print $Q$ lines containing the answer to each query, one per line.

Examples

Input 1

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

Output 1

6
3
9