$N$ 個の頂点からなる木（サイクルを持たない無向連結グラフ）がある。頂点には $1$ から $N$ までの番号が、辺には $1$ から $(N-1)$ までの番号が付けられている。

以下のクエリを処理するプログラムを作成せよ。

• $u$ $v$ : 頂点 $x$ ($1 \le x \le N$) について、$\operatorname{dist}(x, u) + \operatorname{dist}(x, v)$ の最大値を出力する。 ($1 \le u, v \le N$)

ここで、$\operatorname{dist}(x, y)$ は頂点 $x$ から頂点 $y$ への最短経路上の辺の数として定義される。木のすべての頂点 $x$ について $\operatorname{dist}(x, x) = 0$ である。

入力

1行目に木の頂点数 $N$ が与えられる。 ($2 \le N \le 300000$)

続く $(N-1)$ 行には木の情報が与えられる。そのうち $i$ 行目には、$i$ 番目の辺が接続する2つの頂点番号が空白区切りで与えられる。

次の行にクエリの数 $Q$ が与えられる。 ($2 \le Q \le 300000$)

続く $Q$ 行には、クエリの情報が1行ずつ与えられる。

出力

$Q$ 行にわたり、各クエリの答えを順に出力せよ。

入出力例

入力 1

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

出力 1

6
5
5