文理学院程序设计在线练习


Sneakers

Time Limit: 5 Second(s)    Memory Limit: 32 MB

Total Submission(s): 38   Accepted Submission(s): 7
Problem Description

In some world there are N cities and N-1 roads that connect two cities. All cities are connected. Someone had bought a pair of skate-shoes. He wanted to rub through some route in the demon’s step with his skate-shoes. Now he had selected some route but had no idea that how much damage his skate-shoes will take on these routes. Luckily the “Friction Value” of each road is known. Fraction generates heat. The more heat is accumulated, the more damage will caused to the skate-shoes. So the damage value of each road will be Heat Value * Fraction Value. Assumed that the skate-shoes have the initial Heat Value of 1. Each road he runs through will +1 on the Heat Value. Now here are M routes for you to calculate the damage.

Input

An integer T in the first line, indicates the number of test data group(T<=10).
Then follows T groups of test data.
In each group: an integer N in first line indicates the number of cities(Nodes are numbered from 1 to N),(1<=N<=100000).
In the following N-1 lines, there are 3 integers (a,b,c) in each line indicates there is a road between node a and node b, with Fraction Value c (0<=c<=100000).
Then an integer M, indicates the number of routes (1<=M<=100000).
In the following M lines, 2 integers u and v are include in each line indicates one route. For each route please calculate the damage value from node u to node v (The initial heat value of each route is 1).

Output

M lines for each group of data. One result in each line.

Sample Input
2
4
1 2 1
2 3 2
3 4 3
2
1 4
3 4
5
1 5 1
2 4 2
2 3 3
1 2 4
2
1 3
2 5
Sample Output
14
3
10
6
Source

2014市赛