Bajtazar has purchased a piece of the Stubit Forest and is planning to organize a rope park there. He has already selected $n$ very tall trees. He plans to build one platform on each of them. A platform is a flat wooden structure. Each platform is attached to a tree at a certain height (measured in meters from the ground level), which must be a positive integer. Choosing these heights for the individual platforms is the task that keeps Bajtazar awake at night. He is only comforted by the fact that the selected trees are truly very tall, and on each of them, a platform can easily be placed at any height between $1$ and $n$ meters.

Bajtazar has already planned a network of $n - 1$ rope connections between the individual platforms. Each rope connection will allow movement in both directions between the platforms it connects. Bajtazar's plan allows for travel between any two platforms using a sequence of rope connections.

If a rope connection is planned between a pair of platforms, these platforms must have different heights, because otherwise, moving between them would be quite uninteresting. Furthermore, for some rope connections, Bajtazar has already planned which way one will be able to slide down and which way to climb up, meaning which of the connected platforms must be placed higher than the other.

The number of certifications and inspections necessary to open the rope park is directly proportional to the maximum height at which the platforms are placed. Therefore, Bajtazar would like to know the smallest natural number $M$ such that his plan can be realized without placing any of the platforms at a height greater than $M$ meters.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 25\,000$) denoting the number of independent data sets to consider. The following lines contain the descriptions of the data sets.

The first line of each description contains a single integer $n$ ($2 \le n \le 200\,000$) denoting the number of trees (and platforms to be built). The trees are numbered from $1$ to $n$.

The next $n - 1$ lines contain information about the rope connections; the $i$-th of these lines contains three integers $a_i, b_i$ and $d_i$ ($1 \le a_i \neq b_i \le n, 0 \le d_i \le 1$); meaning that there is to be a connection between the platform on tree $a_i$ and the platform on tree $b_i$. The platforms $a_i$ and $b_i$ must have different heights. Furthermore, if $d_i = 1$, then the platform $a_i$ must be lower than the platform $b_i$.

The sum of the values of $n$ for all data sets in a single test does not exceed $200\,000$.

Output

For each data set, output in a single line the minimum number $M$ for which a correct placement of the platforms exists.

Examples

Input 1

1
4
1 2 1
1 3 0
4 1 1

Output 1

3

Note

Explanation of the example: For $M = 3$, a correct placement of the platforms is: tree 1 at height 2, tree 2 at height 3, tree 3 at height 1 or 3, tree 4 at height 1. There is no correct placement of the platforms for $M \le 2$.

Evaluation tests

• 1ocen: a single data set with $n = 1023 = 2^{10} - 1$; for every $k = 1, 2, \dots, 2^9 - 1$, platform $k$ must be lower than platform $2 \cdot k$ and at a different height than platform $2 \cdot k + 1$; the answer is $M = 10$.
• 2ocen: a single data set with $n = 50\,000$, in which each tree has at most two connections.
• 3ocen: three data sets with values of $n$ chosen from the range $[60\,000, 70\,000]$; every connection satisfies $d_i = 1$ and connects platform 1 with another platform.

Subtasks