Khoảng cách trên cây

Cây là đồ thị vô hướng liên thông không chứa chu trình. Một cây gồm \(n\) đỉnh luôn có \(n - 1\) cạnh và giữa hai đỉnh phân biệt trên cây luôn tồn tại đường đi đơn duy nhất. Cho một cây gồm \(n\) đỉnh và mỗi cạnh của cây có một độ dài riêng. Bạn cần trả lời \(q\) câu hỏi, mỗi câu hỏi gồm hai đỉnh \(u, v\) và bạn cần cho biết khoảng cách giữa hai đỉnh \(u\) và \(v\). Nói cách khác, bạn cần tính tổng độ dài các cạnh thuộc đường đi đơn duy nhất từ \(u\) đến \(v\).

Input

Dòng đầu tiên chứa số nguyên \(θ\) \((1 ≤ θ ≤ 3)\) --- số thứ tự của subtask chứa test này.

Dòng thứ hai chứa một số nguyên \(n\) \((1 ≤ n ≤ 3·10^5)\) --- số đỉnh của cây.

\(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(c\) \((1 ≤ u, v ≤ n, 1 ≤ c ≤ 10^9)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\) với độ dài \(c\).

Dòng tiếp theo chứa một số nguyên \(q\) \((1 ≤ q ≤ 3·10^5)\) --- số câu hỏi cần trả lời.

\(q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 ≤ u, v ≤ n)\) thể hiện một câu hỏi.

Output

In ra \(q\) số nguyên là khoảng cách giữa hai đỉnh \(u\) và \(v\) trên cây trong mỗi câu hỏi.

Example

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

19
4
14

Scoring

Subtask \(1\) (\(35\) điểm): \(n, q ≤ 300\).

Subtask \(2\) (\(25\) điểm): Cây có \(n - 1\) cạnh \((1, 2), (2, 3), ..., (n - 1, n)\).

Subtask \(3\) (\(40\) điểm): Không có ràng buộc gì thêm.