题目描述

​ 刘桑是个黑心商人，他经常低价收购一些残次品然后以次充好再卖出去，这天刘桑来到了Y桑的杂货铺，准备坑Y桑一把。

​ Y桑贩卖的是龙珠，每个龙珠上都有一个编号，编号不是唯一的，同一个编号可能会出现在不同的龙珠上。Y桑是一对一对卖的，他把两个龙珠捆绑在一起售卖。

​ 黑心商人刘桑骗Y桑说他的龙珠都是赝品，但是他愿意承担这些赝品。Y桑被唬住了，他十分感激刘桑，并表示刘桑买了多少龙珠，他就赠送刘桑所买的龙珠编号里没有的龙珠。也就是说，如果刘桑购买了2号和5号龙珠，Y桑就会额外赠送他3号和4号龙珠，如果刘桑买了4号，6号，9号龙珠，Y桑就会额外赠送他5,7,8号龙珠。

​ 这样一来黑心商人刘桑就打起了小算盘，他想以最低的价格获得更多的龙珠。请你帮刘桑算一下，他想要获得更多的不同编号的龙珠最少需要花费多少金币

输入格式

第一行包含一个整数 $t$，表示测试案例的数量。

每组测试案例的第一行有一个数字 $n$ ($1 \le n \le 10^5$),表示Y桑贩卖龙珠的对数。

接下来 $n$ 行，每一行都有三个整数 $l_i, r_i, c_i$ 表示这一对龙珠的两个编号，以及购买这一对龙珠所需要的金币

保证所有测试案例中$n$之和不超过$2 \cdot 10^5$。

输出格式

每个测试案例输出 $n$ 行

每一行一个整数，表示前 $i$ ($1 \leq i \leq n$)对龙珠中，刘桑想要获得更多龙珠的最少金币花费。

样例

样例输入1

3
2
2 4 20
7 8 22
2
5 11 42
5 11 42
6
1 4 4
5 8 9
7 8 7
2 10 252
1 11 271
1 10 1

样例输出1

20
42
42
42
4
13
11
256
271
271

样例解释

• 在第一个测试案例中，前1对龙珠里，刘桑只能买第一对龙珠，最终花费20金币获得3颗不同的龙珠。

  前2对龙珠中，刘桑可以买下这两对龙珠，最终花费42金币获得7颗不同的龙珠。

• 在第二个测试案例中，无论前几对龙珠，刘桑都只会买一对龙珠，因为它们是相同的，最终花费42金币获得7颗不同的龙珠。

• 在第三个测试案例中，前3对龙珠里，刘桑可以选择购买第1对和第3对 $[1,4,7,8]$ 龙珠，Y桑又赠送给他 $[2,3,5,6]$ 龙珠，最终花费11金币获得8颗不同的龙珠。