Countries C and D have been at war for years.

Recently, Country C successfully infiltrated a city in Country D. This city can be abstracted as an undirected graph with $n$ nodes and $n-1$ edges, such that any two nodes are reachable from each other; in other words, this undirected graph is actually a tree.

After reconnaissance, GGB, the head of Country C's intelligence department, was surprised to find that this inconspicuous city is actually a military center for Country D. Therefore, GGB decided to set up intelligence agencies within this city. After investigation, intelligence expert TAC arranged $m$ schemes for setting up intelligence agencies. In these schemes, the $i$-th scheme involves arranging intelligence personnel to collect information along all edges on the shortest path from node $x_i$ to node $y_i$, and this scheme costs $v_i$.

However, due to a shortage of personnel, GGB can only implement two of the $m$ schemes mentioned above. At the same time, TAC pointed out that for these two intelligence agencies to cooperate better, their information collection ranges must share at least one common edge. To evaluate the performance of a scheme, GGB and TAC surveyed all edges and assigned an intelligence value $c_i$ to each edge, representing the profit of $c_i$ obtained by collecting information on that edge. Note that information is unique, so when the information of an edge is collected by two intelligence agencies, it still only yields a profit of $c_i$.

Now, please help GGB choose two legal schemes to implement such that the information collection ranges of these two schemes share at least one common edge, and on this basis, the difference between the total profit and the total cost is maximized. Note that this value may be negative, but it is still legal. If no such two schemes can be found, please output F.

Input

The first line contains an integer $T$, representing the number of test cases. Each test case contains $(n + m + 1)$ lines: The first line contains an integer $n$, representing the number of nodes in the city. In the next $n-1$ lines, the $(i+1)$-th line contains three integers $a_i, b_i, c_i$, representing an undirected edge in the city connecting nodes $a_i$ and $b_i$ with an intelligence value of $c_i$. It is guaranteed that $a_i < b_i$ and all $b_i$ are distinct. The $(n+1)$-th line contains an integer $m$, representing the $m$ schemes for setting up intelligence agencies proposed by TAC. In the next $m$ lines, the $(n+i+1)$-th line contains three integers $x_i, y_i, v_i$, representing that the $i$-th scheme for setting up an intelligence agency involves arranging intelligence personnel to collect information along all edges on the shortest path from node $x_i$ to node $y_i$, with a cost of $v_i$.

Output

For each test case, output one line: if a legal pair of schemes exists, output an integer representing the maximum difference between the total profit and the total cost; otherwise, output F.

Examples

Input 1

2
5
1 2 1
2 3 3
3 4 2
1 5 8
2
1 4 5
3 5 8
5
1 2 1
2 3 3
3 4 3
1 5 9
2
1 5 5
2 3 8

Output 1

1
F

Note 1

This example contains two test cases. The cities in these two test cases are the same, but the intelligence values and the schemes for the intelligence agencies are different. The city map is as follows:

• For the first test case, the shortest path from node 1 to node 4 in scheme 1 is $1 \to 2 \to 3 \to 4$, and the shortest path from node 3 to node 5 in scheme 2 is $3 \to 2 \to 1 \to 5$. Choosing these two schemes requires a cost of $5 + 8 = 13$, and all edges' information is collected, resulting in a profit of $1 + 3 + 2 + 8 = 14$. Therefore, the total profit minus the total cost is $14 - 13 = 1$.
• For the second test case, the shortest path from node 1 to node 5 in scheme 1 is $1 \to 5$, and the shortest path from node 2 to node 3 in scheme 2 is $2 \to 3$. These two schemes have no common edges in their information collection ranges, so they are illegal. Therefore, this test case has no legal schemes, and F should be output.

Examples 2

See center/center2.in and center/center2.ans in the contestant's directory. This example contains only one test case. In this data, the optimal solution is to choose the 2nd and 3rd schemes. The city map for this data is as follows:

Examples 3

See center/center3.in and center/center3.ans in the contestant's directory. This example has the same properties as the 4th test point.

Examples 4

See center/center4.in and center/center4.ans in the contestant's directory. This example contains specially constructed test data with $n \le 100, m \le 200$, covering all combinations of properties that appear in the test points.

Subtasks

The special properties in the table are as follows: Special property $S_1$: For any $i, j$, it is guaranteed that the node with the smallest index on the shortest path from $x_i$ to $y_i$ is different from the node with the smallest index on the shortest path from $x_j$ to $y_j$. Special property $S_2$: For any $i$, it is guaranteed that the node with the smallest index on the shortest path from $x_i$ to $y_i$ is node 1.

For all data, $1 \le n \le 5 \times 10^4$, $0 \le m \le 10^5$, $0 \le c_i \le 10^9$, $0 \le v_i \le 10^{10} \times n$. In each test point, the sum of all $n$ does not exceed $1,000,233$, and the sum of all $m$ does not exceed $2,000,233$.