Description

Given a tree with $n$ nodes, answer $Q$ queries. Each query asks for the distance between two nodes $x$ and $y$.

Input Format

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

Next, $n-1$ lines follow, each with two integers $x$ and $y$, indicating an edge between nodes $x$ and $y$;

Then an integer $Q$, representing the number of queries;

Finally, $Q$ lines follow, each with two integers $x$ and $y$, representing a query for the distance between $x$ and $y$.

Output Format

Output $Q$ lines, each containing the answer to the corresponding query.

Sample 1

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

3
4

Constraints and Hints

For all data, $1\le n\le 10^5,1\le x,y\le n$.