给定一棵包含 $N$ 个顶点的树（一个无环的连通无向图）。顶点从 $1$ 到 $N$ 编号，边从 $1$ 到 $(N-1)$ 编号。

编写一个程序来处理以下查询。

• $u$ $v$：对于顶点 $x$（$1 \le x \le N$），输出 $\operatorname{dist}(x, u) \times \operatorname{dist}(x, v)$ 的最大值。（$1 \le u, v \le N$）

这里，$\operatorname{dist}(x, y)$ 定义为从顶点 $x$ 到顶点 $y$ 的最短路径上的边数。对于任意顶点 $x$，$\operatorname{dist}(x, x) = 0$。

输入格式

输入的第一行包含一个整数 $N$，表示树的顶点数。（$2 \le N \le 300\,000$）

接下来的 $(N-1)$ 行包含树的信息。其中第 $i$ 行包含两个空格分隔的整数，表示由边 $i$ 连接的两个顶点。

下一行包含一个整数 $Q$，表示查询的次数。（$2 \le Q \le 300\,000$）

接下来的 $Q$ 行，每行包含一个查询的信息，格式与题目描述中所述相同。

输出格式

输出 $Q$ 行，每行包含一个查询的答案。

样例

输入样例 1

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

输出样例 1

6
3
9