在 Byteozavodsk 有 $n$ 个十字路口（编号为 $1$ 到 $n$），它们之间由 $(n-1)$ 条双向街道连接。在任意两个十字路口之间，如果不重复经过任何街道，只有唯一的一条路径。

你需要规划城市的公交线路。一条公交线路的起点和终点必须是满足以下条件的十字路口：该路口仅与一条街道相连。起点和终点必须不同。

每条街道都有一个容量：即可以通过该街道的公交线路数量。

请计算在 Byteozavodsk 可以安排的公交线路的最大数量。虽然这可能没什么意义，但确实可以有两条公交线路连接完全相同的两个十字路口。

输入格式

第一行包含一个整数 $z$，表示测试用例的数量。接下来描述 $z$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示 Byteozavodsk 的十字路口数量。接下来的 $(n-1)$ 行描述城市街道，每行包含三个整数 $a, b, c$ ($1 \le a, b \le n, a \neq b, 1 \le c \le 10^6$)，表示一条连接十字路口 $a$ 和 $b$ 的街道，其容量为 $c$。

输出格式

对于每个测试用例，输出一行，包含一个整数：在 Byteozavodsk 可以安排的公交线路的最大数量。

样例

输入 1

3
4
1 2 2
1 3 2
1 4 2
2
1 2 2
3
1 2 2
2 3 1

输出 1

3
2
1