Mr. Nežmah 有一棵拥有 $n$ 个节点的树。每条边 $(u_i, v_i)$ 上都有一个数字 $a_i$。Nežmah 注意到一个有趣的性质：每个 $a_i$ 的值最多在六条边上出现。

对于任意一对节点 $u$ 和 $v$，我们定义它们的美妙度为：未在 $u$ 到 $v$ 的路径上的任何边上出现的最小非负整数。请找出所有节点对中美妙度的最大值。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 10^5$)。

接下来的 $n - 1$ 行，每行包含三个整数 $u_i$，$v_i$ 和 $a_i$ ($1 \le u_i, v_i \le n$，$u_i \ne v_i$，$0 \le a_i < n$)。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，表示所有节点对中美妙度的最大值。

样例

输入样例 1

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

输出样例 1

2
3
4