Legend

Xiao Chang and Xiao Ming live in a tree with $n$ nodes numbered from $1$ to $n$ . There are a number of kingdoms in the tree.

If a node has more than two edges, then a kingdom appears at that node with the same number as the node (at least one such node is guaranteed to exist). The capital of the kingdom is this node. The kingdom expands its territory as much as possible on a ``first come, first served'' basis. In other words, an unoccupied node will be occupied by the kingdom whose capital is the closest to the node (if there is more than one, the one with the smallest number).

Xiao Chang and Xiao Ming are friends, so Xiao Chang will often visit Xiao Ming, and on the way, he may pass the territories of several kingdoms. Also, to save time, Xiao Chang will follow the shortest path to reach Xiao Ming's home. Now you need to answer $q$ queries, given $u$ and $v$, assuming that Xiao Chang lives in $u$ and Xiao Ming lives in $v$, how many kingdoms will Xiao Chang visit on his way to visit Xiao Ming?

Input format

The first line contains a positive integer $n$, indicating the number of nodes in the tree.

The next $n - 1$ lines, each containing two positive integers $x, y$, indicate the existence of an edge between node $x$ and node $y$.

The $n + 1$th line contains a positive integer $q$, indicating the number of queries.

The next $q$ lines, each containing two positive integers $u, v$, describe a single query.

$4\leq n \leq 2\times 10^5$ $1\leq q \leq 2\times 10^5$ $1\leq x,y \leq n$ $1\leq u,v \leq n$

Output format

For each query, output a line containing an integer indicating the answer.

6
1 10 10
1 10 -10
1 10 0
2 30
3 30
3 20

120
150
0