Ellen is a student at RHHS who is trying to navigate her way through the school to get to her classes. She knows that most halls are going to be blocked off by large groups of aimless students, so she has devised a map of the school which only includes hallways she knows will be open. In particular, the school can be represented as a collection of ~N~ classrooms numbered ~0~ to ~N - 1~ with ~N - 1~ hallways between them. It is guaranteed that these hallways will never form a loop.

Because Ellen is travelling around the school a lot, she wants to know how far it is between various different locations in the school, so she can plan how long it will take to walk between them.

To help her with this, you will be given ~Q~ queries; for each one you must determine the distance between the two given classrooms.

Input Specification

The first line will contain ~N~ ~(3 \leq N \leq 6\,000)~, the number of classrooms.

The next ~N - 1~ lines will contain three space-separated integers, ~a_i~, ~b_i~, ~w_i~, ~(0 \leq a_i,b_i \leq N - 1, 1 \leq w_i \leq 500\,000)~, indicating that there is a hallway between classrooms ~a_i~ and ~b_i~ with length ~w_i~.

The next line will contain ~Q~ ~(1 \leq Q \leq 1\,000\,000)~, the number of queries to be answered.

The next ~Q~ lines will contain two space-separated integers, ~u_i~ and ~v_i~ ~(0 \leq u_i, v_i \leq N - 1)~, representing a query that asks the distance between classrooms ~u_i~ and ~v_i~.

For test cases worth 20 of 100 points, ~3 \leq N \leq 500~ and ~1 \leq Q \leq 10\,000~.

For test cases worth an additional 20 points, ~3 \leq N \leq 500~.

Output Specification

For each query, output a single integer on its own line which is the distance between the two classrooms in the query.

Sample Input

5
0 1 3
0 3 2
0 4 7
1 2 5
4
2 0
1 4
3 1
3 4

Sample Output

8
10
5
9