Cheap Tourist

The country of Byteland is divided into N provinces numbered from 1 to N. The provinces are connected via N-1 bidirectional roads in a way that it is possible to reach each province from every other province by using one or more of these roads. Candyman is a cheap tourist who wants to visit every province starting from 1 to N in order. Therefore, he starts from province 1, travels to province 2, from province 2, he travels to province 3, so on and so forth until he reaches province N where his journey ends.

In order to travel between two provinces, he needs to purchase a traveler’s pass ticket. There are two types of tickets for each road: single-pass, and multiple-pass. A single-pass ticket expires each time Candyman uses its corresponding road and he needs to purchase it again if he wishes to use that particular road in the future. A multiple-pass ticket, however, does not expire and can be used as many times as necessary for a particular road.

As you can already imagine, both types of passes have two different costs associated with them. For each road ‘i’, a single-pass ticket costs Si bitcoins, and a multiple-pass ticket costs Mi bitcoins. For this problem, you have to help Candyman to figure out the minimum total cost for finishing his travel routes.

Input

The first line of input contains $T$ ($1 \le T \le 10$), the number of test cases.

The first line of each test contains an integer $N$ ($2 \le N \le 200000$), the number of provinces in Byteland. Each of the following $N-1$ lines contains four integers, $U$, $V$, $Si$, $Mi$, denoting, there’s a bidirectional road between provinces$U$ and $V$, and the bitcoin costs of single-pass and multiple-pass tickets for this road respectively. Here, $1 \le U$, $V \le N$ and $1 \le Si \le Mi \le 100000$.

Output

For each test case, print a line containing the minimum bitcoin amount Candyman needs to finish his journey.

Sample

Input	Output
3 4 1 2 3 5 1 3 2 4 2 4 1 3 4 1 4 5 5 3 4 4 7 2 4 2 6 5 1 2 2 3 1 3 2 3 1 4 2 3 1 5 2 3	10 16 11

Large dataset, please use faster IO operations.