Description

给定一棵有n个结点的树，Q个询问，每次询问点x到点y两点间的距离。

Format

Input

第一行一个整数n（0<n<=100 000），表示这棵树有n个结点。接下来n-1行，每行两个整数 x，y，表示x，y之间有一条连边。然后一个整数Q，表示有Q个询问，接下来Q行每行两个整数 x,y ,表示询问 x 到 y 的距离。

Output

输出Q行，每行表示每个询问的结果。

Sample 1

Input

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

Output

3
4

Limitation

1s, 64MiB for each test case.

Source