M. Greedy Pirate
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given n islands numbered from 1 to n and connected using n - 1 magical bridges. A greedy pirate wants to collect as many coins as possible by traveling through the bridges. Each bridge is a two-way bridge, but the pirate can only use the bridge at most twice. If a bridge connects islands u and v, then going from u to v gives c1 coins, and going from v to u gives c2.

Help the pirate to collect as many coins as he can knowing that he will start from some island x and finish at some island y.

Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains one integer n (2 ≤ n ≤ 105), in which n is the number of islands. The n - 1 lines follow, giving the bridges. Each line contains four integers u, v, c1, and c2 (1 ≤ u, v ≤ n, 1 ≤ c1, c2 ≤ 104), as describing in the statement above.

The next line contains an integer q (1 ≤ q ≤ 105), in which q is the number of queries. Then q lines follow, giving queries. Each query consists of two integers x and y (1 ≤ x, y ≤ n), in which x and y are the starting and finish islands, respectively.

The sum of n and q overall test cases does not exceed 25 × 105 for each.

Output

For each query, print a single line containing the maximum amount of money the greedy pirate can collect by traveling through the bridges starting from island x and finishing at island y.

Example
Input
1
5
1 2 5 10
3 5 25 3
4 2 15 12
3 2 6 7
2
1 5
4 3
Output
64
65