Weighted Tree Path Sum

You are given an undirected weighted tree with N nodes numbered from 1 to N. The tree is defined by N-1 edges, where each edge connects two nodes u and v with a positive weight w.

Your task is to answer Q queries. In each query, given two nodes a and b, determine the sum of the weights along the unique simple path between a and b.

Note: Since the graph is a tree, there is exactly one simple path between any pair of nodes. The answer for a query where a equals b is 0.

The input consists of multiple test cases.

The answer for each query should be printed on a separate line to standard output.

In mathematical terms, if the unique path from node a to node b is given by the sequence of edges with weights \(w_1, w_2, \dots, w_k\), your answer is \(\sum_{i=1}^{k}w_i\).

inputFormat

The first line contains an integer T representing the number of test cases.

For each test case, the input is given as follows:

1. A line containing an integer N denoting the number of nodes in the tree.
2. N-1 lines follow, each containing three integers u, v and w representing an edge between nodes u and v with weight w.
3. A line containing an integer Q representing the number of queries.
4. Q lines follow, each containing two integers a and b for which you must compute the path sum.

All input is read from standard input (stdin).

outputFormat

For each query, output the sum of the weights along the unique path between the given nodes. Each answer should be printed on a separate line to standard output (stdout).

## sample

3
4
1 2 4
2 3 6
2 4 5
2
1 3
4 3
2
1 2 10
1
1 2
1
1
1 1

10
11
10
0

</p>