Description

庞博士有 $3$ 项技能：喝汽水、猎狐和炒股，编号分别为 $1,2,3$。初始时，每项技能的熟练度为 $0$。

接下来有 $n$ 天。在第 $i$ 天，庞博士可以选择一项技能（假设是第 $j$ 项）进行练习，然后在这天结束时让这项技能的熟练度增加 $a_{i,j}(0\leq a_{i,j}\leq 10000)$。同时，如果某一项技能（假设是第 $k$ 项）已经有 $x$ 天没有练习，那么在这天结束时，这项技能的熟练度会减少 $x$。当然，任何一项技能的熟练度都不可能小于 $0$。

现在，庞博士想知道：在第 $n$ 天结束后，这 $3$ 项技能的熟练度之和最大为多少。由于他非常忙，而且他的日程和对习惯的适应程度可能有变，所以庞博士把这 $T$ 个问题交给了你——每个问题的内容都一样，只是给出的数据可能有所不同而已。

Input Format

第一行，一个正整数 $T~(1 \leq T \leq 1000)$，表示数据组数。

对于每组数据，输入 $(n + 1)$ 行。

• 第一行，一个正整数 $n\ (1 \leq n \leq 1000)$，表示天数。
• 第 $i + 1$ 行，包含三个正整数 $a_{i, 1}, a_{i, 2}, a_{i, 3}\ (0 \leq a_{i, j} \leq 10000,\ \forall 1 \leq i \leq n,\ 1 \leq j \leq 3)$。

数据保证单个测试点内的 $\sum n$ 不超过 $1000$。

Output Format

对于每组数据，输出 $1$ 行 $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

26
41