Tree

A weighted tree is given. Find the distance between two specified vertices.

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.

Examples