Bajtazar 买下了一片比特森林，并计划在其中建造一个绳索公园。他已经选好了 $n$ 棵非常高的树，并计划在每棵树上建造一个平台。平台是一个平坦的木质结构。每个平台都固定在树上，高度（从地面算起，单位为米）为一个正整数。为每个平台选择合适的高度是让 Bajtazar 头疼的问题。唯一让他感到欣慰的是，选定的树确实非常高，每棵树上的平台都可以轻松地放置在 $1$ 到 $n$ 米之间的任意高度。

Bajtazar 已经规划好了平台之间的 $n - 1$ 条绳索连接。每条绳索连接都允许在相连的两个平台之间双向通行。Bajtazar 的计划保证了可以通过绳索连接在任意两个平台之间通行。

如果两个平台之间计划有绳索连接，则这两个平台必须具有不同的高度，否则通行会变得毫无趣味。此外，对于某些绳索连接，Bajtazar 已经规划好了滑行和攀爬的方向，即规定了其中一个平台必须比另一个平台更高。

绳索公园开放所需的认证和检查数量与平台放置的最大高度成正比。因此，Bajtazar 想知道最小的自然数 $M$，使得他的计划可以实现，且没有任何平台的高度超过 $M$ 米。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 25\,000$)，表示需要考虑的独立测试用例的数量。接下来的行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示树（以及要建造的平台）的数量。树的编号从 $1$ 到 $n$。

接下来的 $n - 1$ 行包含有关绳索连接的信息；其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $d_i$ ($1 \le a_i \neq b_i \le n, 0 \le d_i \le 1$)，表示在树 $a_i$ 上的平台和树 $b_i$ 上的平台之间存在连接。平台 $a_i$ 和 $b_i$ 必须具有不同的高度。此外，如果 $d_i = 1$，则平台 $a_i$ 必须低于平台 $b_i$。

单个测试中所有测试用例的 $n$ 之和不超过 $200\,000$。

输出格式

对于每个测试用例，在单独的一行中输出最小的 $M$，使得存在合法的平台放置方案。

样例

输入 1

1
4
1 2 1
1 3 0
4 1 1

输出 1

3

说明 1

对于 $M = 3$，一种合法的平台放置方案为：树 $1$ 在高度 $2$，树 $2$ 在高度 $3$，树 $3$ 在高度 $1$ 或 $3$，树 $4$ 在高度 $1$。 不存在 $M \le 2$ 的合法放置方案。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。