题目描述

给定一棵包含 $N$ 个顶点的树。顶点编号为 $1,2,\ldots,N$。

你需要回答若干次询问。每次询问给出两个顶点 $u,v$，求

$$\max_{1\le x\le N} \bigl(\operatorname{dist}(x,u)+\operatorname{dist}(x,v)\bigr).$$

其中 $\operatorname{dist}(x,y)$ 表示树上从顶点 $x$ 到顶点 $y$ 的最短路径所包含的边数，并规定

$$\operatorname{dist}(x,x)=0.$$

输入格式

第一行输入一个整数 $N$，表示树的顶点数。

$$2\le N\le 300000.$$

接下来 $N-1$ 行，每行输入两个整数，表示树中的一条边。

随后一行输入询问数 $Q$。

$$2\le Q\le 300000.$$

接下来 $Q$ 行，每行输入两个整数 $u,v$，表示一次询问。

输出格式

对每次询问输出一行答案。

样例

输入

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

输出

6
5
5