还有不到 1000 个星期就要高考了！为了帮你刚出生的学弟备战高考，你决定帮他制定一个训练计划。
在每个星期，他可以选择数竞、物竞、文化课中的一个进行训练，分别记为课程 $1,2,3$ 。如果在第 $i$ 个星期选择了第 $j$ 门课程，他在第 $j$ 门课程的水平就会提高 $a_{i,j}$ 。初始三门课程的水平都是 $0$ 。
一门课程太久没学就会水平下降。在每个星期结束的时候，如果他已经连续 $k$ 个星期（包括这个星期）没有学习第 $j$ 门课程了，那么他在第 $j$ 门课程的水平就会下降 $k$ 。比如他某三个星期分别学习了 $3,1,2$ ，那么在第三个星期结束时第 $1$ 门课程的水平会下降 $1$ ，而第 $3$ 门课程的水平会下降 $2$ 。特别的，单门课的水平不会降到 $0$ 以下。
你希望你的学弟全面发展，所以你希望最大化他在高考时三门课程的水平之和。
输入格式
第一行一个正整数 $T$ ，表示数据组数。每组数据的格式如下：
- 第一行一个正整数 $n$ ，表示距离高考还有几个星期。
- 接下来 $n$ 行，每行三个非负整数 $a_{i,1},a_{i,2}，a_{i,3}$ .
输出格式
对每组数据输出一行一个非负整数，表示答案。
样例 1
input
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
output
26 41
样例 2
见下发文件。
数据范围
对于所有数据，保证 $1\le T\le 1000,1\le n,\sum n\le 1000,0\le a_{i,j}\le 10^4$ 。
| 子任务编号 | $\sum n\le $ | $a_{i,j}\le $ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $200$ | $ $ | / | $20$ |
| $2$ | $ $ | $ $ | $a_{i,j}$ 在范围内随机生成 | $25$ |
| $3$ | $800$ | $10^3$ | / | $25$ |
| $4$ | $ $ | $ $ | / | $30$ |
时间限制：$\texttt{2s}$
空间限制：$\texttt{1024MB}$