There are less than 1000 weeks left until the Gaokao! To help your newborn junior prepare for the exam, you decide to create a training plan for them.

Each week, they can choose to study for one of three subjects: Mathematics Olympiad, Physics Olympiad, or regular coursework, denoted as courses $1, 2, 3$. If they choose course $j$ in week $i$, their proficiency in course $j$ increases by $a_{i,j}$. The initial proficiency for all three courses is $0$.

If a course is not studied for too long, the proficiency in that subject will decrease. At the end of each week, if they have not studied course $j$ for $k$ consecutive weeks (including the current week), their proficiency in course $j$ will decrease by $k$. For example, if they studied subjects $3, 1, 2$ in three consecutive weeks, then at the end of the third week, the proficiency in course $1$ will decrease by $1$, and the proficiency in course $3$ will decrease by $2$. Specifically, the proficiency of a single course will not drop below $0$.

You want your junior to develop comprehensively, so you wish to maximize the sum of their proficiencies in the three courses at the time of the Gaokao.

Input

The first line contains a positive integer $T$, representing the number of test cases. The format for each test case is as follows:

• The first line contains a positive integer $n$, representing the number of weeks until the Gaokao.
• The next $n$ lines each contain three non-negative integers $a_{i,1}, a_{i,2}, a_{i,3}$.

Output

For each test case, output a single line containing a non-negative integer representing the answer.

Examples

Input 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

Output 1

26
41

Input 2

See the provided files.

Constraints

For all data, it is guaranteed that $1 \le T \le 1000$, $1 \le n$, $\sum n \le 1000$, and $0 \le a_{i,j} \le 10^4$.