有 $n$ 种类型的男孩和 $2 \cdot n$ 个女孩。男孩的类型用从 $1$ 到 $n$ 的整数编号，而女孩用从 $1$ 到 $2 \cdot n$ 的整数编号。

第 $i$ 种类型的男孩有 $c_i$ 个，他们每个人都喜欢编号为 $a_i$ 和 $b_i$ 的女孩。

找出一个最大的男孩集合，使得集合中任意一对男孩都至少共同喜欢一个女孩。求这个集合的大小。

在本问题中，每个测试包含多组输入数据。你需要对每组数据独立地解决问题。

输入

第一行包含一个整数 $T$ $(1 \le T \le 500)$~--- 输入数据的组数。接下来是各组输入数据的描述。

每组输入数据的第一行包含一个整数 $n$ $(1 \le n \le 7 \cdot 10^5)$。

接下来的 $n$ 行中，每行有三个整数 $a_i, b_i, c_i$ $(1 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9)$~--- 对应类型男孩的参数。

保证对于任意 $1 \le i < j \le n$，都有 $a_i \ne a_j$ 或 $b_i \ne b_j$。

保证单个测试中所有输入数据集的 $n$ 的总和不超过 $7 \cdot 10^5$。

输出

对于每组输入数据，单独一行输出一个整数~--- 满足集合中任意一对男孩都至少共同喜欢一个女孩的男孩最大集合的大小。

Example

Input

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

Output

5
9
10

评分

设 $S$ 为单个测试中所有测试用例输入集的 $n$ 的总和，设 $K$ 为单个测试中所有测试用例输入集的 $c_i$ 的总和。

1. ($5$ 分): $n \le 5$;
2. ($11$ 分): $S \le 100$;
3. ($7$ 分): 每个女孩最多被两种类型的男孩喜欢；
4. ($10$ 分): $S \le 3000$;
5. ($23$ 分): $S \le 3 \cdot 10^5$;
6. ($19$ 分): $K \le 10^7$;
7. ($25$ 分): 无额外限制。