Tree Distance Queries

You are given a tree with N vertices and N-1 edges. Each edge connects two nodes with a given weight. The tree is undirected and connected, which means there is exactly one unique simple path connecting any two nodes. You will be provided with a set of queries. Each query consists of two vertices, and your task is to compute the distance between these two vertices. The distance between two nodes is defined as the sum of the weights of the edges on the unique path connecting them. Formally, if the tree is denoted by \(G=(V,E)\) and for a query \((a,b)\) the unique path is \(a = v_0, v_1, \ldots, v_k = b\), then the answer is given by:

[ \text{distance}(a, b) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) ]

Read the input from standard input and print the results for each query on a separate line to standard output.

inputFormat

The input starts with an integer T representing the number of test cases. Each test case is described as follows:

• An integer N (number of nodes).
• N-1 lines follow, each containing three integers u, v and w, representing an undirected edge between nodes u and v with weight w.
• An integer Q representing the number of queries.
• Q lines follow, each containing two integers a and b, representing a query asking the distance between nodes a and b.

All input is read from standard input.

outputFormat

For each query, output a single line containing the distance between the two specified nodes. All output should be written to standard output.

## sample

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

7
6

</p>