Hasan the Treasure Hunter

Benjamin Gates the treasure hunter opened a coaching center named Khajna Dibo Na where he teaches his students to learn about treasure hunting. The coaching center is conducted by Benjamin Gates, Riley Pool, Abigail Chase, Patrick Gates and Emily Appleton.

Hasan Abdullah is a student of this coaching center. As he has a great interest in treasure hunting, the Khajna Dibo Na team proposed him to solve an assignment of treasure hunting in order to examine his excellence. They gave Hasan a map which is a treasure map. To gain all the treasures, Hasan needs to answer several queries.

The treasure map consists of several places. All the places are connected by some paths. It’s possible to visit between any two places by these paths. Each path between any two places contains an amount of treasure with weight $C$. There is only one path to go from a single place to another place. Now, Hasan wants to gain all the treasures and he is ready to reply all the queries.

In each query, he will be given any two places suppose $A$ and $B$. It might be possible to travel from place $A$ to place $B$ by crossing more than one places. As each of the places is connected by some paths he will have some treasures in each of the paths of several weights. While traveling, the authority tells him to collect all the treasures and suggests him to convert all the treasure weight into a magic weight. The magic weight is said to be the minimum weight among the treasures he collected. Hasan has to find out what will be the minimum amount of treasures he needs to reduce in order to convert all the treasure weight into the magic weight.

For example, if he has 3 edges of treasure value 3, 2, 5 between two places $A$ and $B$. As the minimum treasure value is 2 in the 2nd edge so the magic weight should be 2. Hasan needs to convert the treasure value of all the edges into 2. And hence he has the minimum amount is $|3 - 2| + |2 - 2| + |5 - 2| = 1 + 0 + 3 = 4$.

Input

Input starts with an integers $N$ ($1 \le N \le 5 \times 10^3$) where N denotes the number of places on the map.

Now, there are $N-1$ lines contains three integers $u$, $v$ ($1 \le u, v \le N$) and $C$ ($1 \le C \le 2 \times 10^5$) that denotes a path between node $u$ and $v$ and the treasure value $C$ of between those two places.

The following line contains an integer $Q$ ($0 \le Q \le 10^5$) which denotes the number of queries is going to be asked.

The following $Q$ lines contain two integers $A$ and $B$ ($1 \le A, B \le N$), denoting for which two places Hasan need to answer the question as stated above.

Output

For each Q line you need to print the required answer of the question i.e. the minimum amount of treasures he needs to reduce in order to convert the treasure weight of all the paths between two places into the magic weight.

Sample

Input	Output
3 1 2 3 2 3 2 2 1 2 1 3	0 1
For query 1, we have only 1 path and hence the amount we need is $3 – 3 = 0$. For query 2, we have 2 paths i.e. 1-2, 2-3 and the minimum coin value is 2. So, the amount we need is $(3-2) + (2 -2) = 1$.