Tree

Input

The first line contains the number of nodes n~(1 \le n \le 150000) in the tree. Nodes are numbered from $0$ to n - 1. Each of the following n - 1 lines consists of three integers u, v, w representing an edge with weight w~(0 \le w \le 1000), connecting nodes $u$ and $v$. The next line contains the number of queries m~(1 \le m \le 75000). Each of the next $m$ lines contains two integers — the numbers of vertices between which the distance needs to be computed.

Output

For each query print the distance between the nodes with the given numbers.

Esempi