There is a country with $n$ cities and $n - 1$ roads. Each city is labeled with an integer from $1$ to $n$, and each road is labeled with an integer from $1$ to $n - 1$. The $i$-th road connects cities $a_i$ and $b_i$ bidirectionally and has a travel cost $w_i$. You can travel between any two cities using the roads.

The distance between two cities is defined as the minimum cost of moving from one city to another.

As the president of a road company, you are planning a discount event for the holidays. There are a total of $q$ plans for the discount event. In the $i$-th plan, the discount is applied to all roads on the shortest path between cities $x_i$ and $y_i$: the travel costs of all these roads become zero. For each discount event plan, compute the maximum value of the distance between any two cities.

Input

The first line contains an integer $n$, the number of cities ($2 \le n \le 10^5$).

The $i$-th of the next $n - 1$ lines contains three integers, $a_i$, $b_i$, and $w_i$: the cities the $i$-th road connects and the road's travel cost ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le w_i \le 10^9$). It is possible to travel between any two cities using the roads.

The next line contains an integer $q$, the number of plans ($1 \le q \le 10^5$).

The $i$-th of the next $q$ lines contains two integers, $x_i$ and $y_i$, describing the $i$-th plan ($1 \le x_i, y_i \le n$, $x_i \neq y_i$).

Output

Print $q$ lines. On the $i$-th line, you should print the answer for the $i$-th query.

Examples

Input 1

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

Output 1

4
4
3

Input 2

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

Output 2

9
7
5

Input 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

Output 3

13
13
16
16
13
16
15

Input 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

Output 4

12
11
11
12
7
11