还有不到 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$ 。

时间限制：$\texttt{2s}$

空间限制：$\texttt{1024MB}$