一个国家有 $n$ 个城市和 $n - 1$ 条道路。每个城市用 $1$ 到 $n$ 的整数标记，每条道路用 $1$ 到 $n - 1$ 的整数标记。第 $i$ 条道路双向连接城市 $a_i$ 和 $b_i$，且其通行代价为 $w_i$。你可以通过这些道路在任意两个城市之间通行。

两个城市之间的距离定义为从一个城市移动到另一个城市的最小代价。

作为一家道路公司的总裁，你正在计划一次节日优惠活动。优惠活动共有 $q$ 个方案。在第 $i$ 个方案中，优惠将应用于城市 $x_i$ 和 $y_i$ 之间最短路径上的所有道路：所有这些道路的通行代价都将变为零。对于每个优惠活动方案，请计算任意两个城市之间距离的最大值。

输入格式

第一行包含一个整数 $n$，表示城市的数量（$2 \le n \le 10^5$）。

接下来的 $n - 1$ 行中，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $w_i$，表示第 $i$ 条道路连接的城市以及该道路的通行代价（$1 \le a_i, b_i \le n$，$a_i \neq b_i$，$1 \le w_i \le 10^9$）。保证可以通过这些道路在任意两个城市之间通行。

下一行包含一个整数 $q$，表示方案的数量（$1 \le q \le 10^5$）。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，描述第 $i$ 个方案（$1 \le x_i, y_i \le n$，$x_i \neq y_i$）。

输出格式

输出 $q$ 行。在第 $i$ 行中，输出第 $i$ 次询问的答案。

样例

输入 1

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

输出 1

4
4
3

输入 2

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

输出 2

9
7
5

输入 3

8
1 2 3
1 3 5
2 4 5
2 5 3
2 6 6
6 7 1
6 8 2
7
1 2
1 3
2 4
2 5
2 6
6 7
6 8

输出 3

13
13
16
16
13
16
15

输入 4

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

输出 4

12
11
11
12
7
11