Pang 教授有 3 种不同的技能可以练习，分别是喝汽水、猎狐和股票投资。我们称它们为技能 1、技能 2 和技能 3。在接下来的 $n$ 天里，Pang 教授每天可以选择其中一种技能进行练习。在第 $i$ 天（$1 \le i \le n$），如果 Pang 教授选择练习技能 $j$（$1 \le j \le 3$），他的技能 $j$ 的等级将增加 $a_{i,j}$。初始时，Pang 教授所有技能的等级均为 0。

Pang 教授如果不练习某项技能，该技能就会退化。在每天结束时，如果他已经有 $k$ 天没有练习技能 $j$，那么他的技能 $j$ 等级将减少 $k$。例如，如果他在第 1 天练习技能 1，在第 2 天练习技能 2，那么在第 2 天结束时，他已经有 1 天没有练习技能 1，有 2 天没有练习技能 3。此时，他的技能 1 和技能 3 的等级将分别减少 1 和 2。他的技能 2 的等级在第 2 天结束时不会减少，因为他在当天练习了技能 2。在这个例子中，我们还知道在第 1 天结束时，他的技能 2 和技能 3 的等级都减少了 1。

Pang 教授任何技能的等级都不会低于 0。例如，如果某项技能的等级为 3，而在某天结束时该等级减少了 4，它将变为 0 而不是 $-1$。

Pang 教授对所有技能一视同仁。因此，他希望在第 $n$ 天结束时，他三项技能等级之和最大。

给定 $a_{i,j}$（$1 \le i \le n, 1 \le j \le 3$），求该最大和。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$（$1 \le n \le 1000$）。接下来的 $n$ 行，每行包含三个整数 $a_{i,1}, a_{i,2}, a_{i,3}$（对于任意 $1 \le i \le n, 1 \le j \le 3$，均有 $0 \le a_{i,j} \le 10000$）。 保证所有测试用例的 $n$ 之和不超过 1000。

输出格式

对于每个测试用例，输出一行，表示技能等级之和的最大可能值。

样例

输入 1

2
3
1 1 10
1 10 1
10 1 1
5
1 2 3
6 5 4
7 8 9
12 11 10
13 14 15

输出 1

26
41