M. Maximum Mex
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Nežmah has a tree with $$$n$$$ nodes. On each edge $$$(u_i, v_i)$$$, there is a number $$$a_i$$$. Nežmah noticed an interesting property: every value of $$$a_i$$$ appears on at most six edges.

For every pair of nodes $$$u$$$ and $$$v$$$, let's define their goodness as the smallest non-negative integer that doesn't appear on any edges on the path from $$$u$$$ to $$$v$$$. Find the maximum value of goodness across all pairs of nodes.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$).

The following $$$n - 1$$$ lines of each test case contain $$$u_i$$$, $$$v_i$$$, and $$$a_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i, 0 \leq a_i \lt n$$$).

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, in a single line, output the maximum value of goodness across all pairs of nodes.

Example
Input
3
4
2 1 0
1 3 1
1 4 2
5
1 2 0
1 3 1
2 4 0
2 5 2
10
2 3 0
6 10 1
3 7 2
10 9 0
8 2 0
1 9 2
5 2 1
9 3 2
4 10 3
Output
2
3
4