题目描述

Prof. Pang has $3$ different skills to practice, including soda drinking, fox hunting, and stock investing. We call them Skill $1$, Skill $2$, and Skill $3$. In each of the following $n$ days, Prof. Pang can choose one of the three skills to practice. In the $i$-th day ($1\le i\le n$), if Prof. Pang chooses Skill $j$ ($1\le j\le 3$) to practice, his level of Skill $j$ will increase by $a_{i,j}$. Initially, Prof. Pang's levels of all skills are $0$.

Prof. Pang forgets skills if he does not practice. At the end of each day, if he has not practiced Skill $j$ for $k$ days, his level of Skill $j$ will decrease by $k$. For example, if he practices Skill $1$ on day $1$ and Skill $2$ on day $2$, at the end of day $2$, he has not practiced Skill $1$ for $1$ day and has not practiced Skill $3$ for $2$ days. Then his levels of Skill $1$ and Skill $3$ will decrease by $1$ and $2$, respectively. His level of Skill $2$ does not decrease at the end of day $2$ because he practices Skill $2$ on that day. In this example, we also know that his levels of Skill $2$ and Skill $3$ both decrease by $1$ at the end of day $1$.

Prof. Pang's level of any skill will not decrease below $0$. For example, if his level of some skill is $3$ and at the end of some day, this level is decreased by $4$, it will become $0$ instead of $-1$.

Prof. Pang values all skills equally. Thus, he wants to maximize the sum of his three skill levels after the end of day $n$.

Given $a_{i,j}$ ($1\le i\le n, 1\le j\le 3$), find the maximum sum.

输入格式

The first line contains a single integer $T~(1 \le T \le 1000)$ denoting the number of test cases.

For each test case, the first line contains an integer $n~(1 \le n \le 1000)$. The $(i+1)$-th line contains three integers $a_{i,1}, a_{i,2}, a_{i,3}$ ($0\le a_{i,j}\le 10000$ for any $1\le i\le n, 1\le j\le 3$).

It is guaranteed that the sum of $n$ over all test cases is no more than $1000$.

输出格式

For each test case, output the maximum possible sum of skill levels in one line.

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