Krzysztof J. 是来自什切青（Szczecin）的一位著名且受人尊敬的黑手党老大。下周，他将组织一次与他的手下们的会议。为了简单起见，我们用数字 $1, 2, \dots, n$ 来表示他们。他们将去吃寿司或打保龄球，然后在晚餐时谈生意。然而，组织这样的活动并非易事，因为受邀的黑手党成员们脾气都相当火爆，他们经常在许多话题上产生分歧，有时甚至会大打出手。这就是他请求你帮助的原因。

你已知恰好有 $n - 1$ 对黑手党成员是朋友，并且对于每一对这样的朋友，你已经确定了他们之间达成直接协议的期望时间。你还建立了一个由朋友关系定义的图。事实证明，该图是连通的，所以对于不是朋友的黑手党成员对，他们达成协议的期望时间是连接他们的图上路径上相邻黑手党成员之间达成直接协议的期望时间之和的最小值。

在晚餐期间，黑手党成员将坐在长桌的一侧。座位的编号为 $1, 2, \dots, w + 1$，其中 $w$ 是桌子的宽度。Krzysztof 不希望在晚餐期间引发任何冲突，因此他决定，如果有一对黑手党成员的座位号分别为 $i$ 和 $j$，且他们达成协议的期望时间为 $d$，则必须满足 $d \le |i - j|$。因此，可能会有一些座位保持空置。你的任务是确定可以安排所有客人就座的桌子的最小宽度。

输入格式

第一行给出一个整数 $Z \le 10^6$，表示后续行中描述的测试用例数量。

每个测试用例的第一行包含一个整数 $n$，表示黑手党成员的数量。接下来的 $n - 1$ 行每行描述一对互为朋友的黑手党成员。第 $i$ 对由三个正整数 $a_i, b_i$ 和 $c_i$ 表示——分别表示黑手党成员的编号以及他们之间达成直接协议的期望时间。

$n \ge 3$，所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，你的程序应该输出桌子的最小宽度。

样例

输入样例 1

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

输出样例 1

2
9