Small L is a member of the school's Algorithm Association. In this year's club recruitment, Small L has recruited $n$ new members, where $n$ is an even number. Now, Small L wants to assign them to different departments in the association.

The Algorithm Association has three departments. The satisfaction of the $i$-th ($1 \le i \le n$) new member for the $j$-th ($1 \le j \le 3$) department is $a_{i,j}$. The satisfaction of an assignment scheme is defined as the sum of the satisfaction of all new members for their assigned departments. That is, if the $i$-th ($1 \le i \le n$) new member is assigned to the $d_i \in \{1, 2, 3\}$-th department, the satisfaction of the assignment scheme is $\sum_{i=1}^n a_{i,d_i}$.

Small L does not want any department to have too many new members. Specifically, he requires that in the assignment scheme, no department is assigned more than $\frac{n}{2}$ new members. You need to help Small L find the maximum possible satisfaction of an assignment scheme that meets his requirements.

Input

This problem contains multiple test cases.

The first line contains a positive integer $t$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$, representing the number of new members.
• The $i+1$-th line ($1 \le i \le n$) contains three non-negative integers $a_{i,1}, a_{i,2}, a_{i,3}$, representing the satisfaction of the $i$-th new member for the 1st, 2nd, and 3rd departments, respectively.

Output

For each test case, output a single line containing a non-negative integer, representing the maximum satisfaction of an assignment scheme that meets Small L's requirements.

Constraints

For all test cases, it is guaranteed that:

• $1 \le t \le 5$;
• $2 \le n \le 10^5$, and $n$ is an even number;
• For all $1 \le i \le n, 1 \le j \le 3$, $0 \le a_{i,j} \le 2 \times 10^4$.

Special Property A: For all $1 \le i \le n$, $a_{i,2} = a_{i,3} = 0$.

Special Property B: For all $1 \le i \le n$, $a_{i,3} = 0$.

Special Property C: For all $1 \le i \le n, 1 \le j \le 3$, $a_{i,j}$ are generated independently and uniformly at random in $[0, 2 \times 10^4]$.

Examples

Input 1

3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0

Output 1

18
4
13

Note

The sample contains three test cases.

For the first test case, we can assign the four new members to departments 1, 3, 1, 2 respectively. The number of new members in the three departments are 2, 1, 1, none of which exceed $\frac{4}{2} = 2$. The satisfaction is $4 + 4 + 5 + 5 = 18$.

For the second test case, we can assign the four new members to departments 1, 1, 2, 2 respectively. The number of new members in the three departments are 2, 2, 0, none of which exceed $\frac{4}{2} = 2$. The satisfaction is $0 + 0 + 2 + 2 = 4$.

For the third test case, we can assign the two new members to departments 2, 1 respectively. The number of new members in the three departments are 1, 1, 0, none of which exceed $\frac{2}{2} = 1$. The satisfaction is $9 + 4 = 13$.

Examples 2-5

See the files club/club2.in through club/club5.in and their corresponding .ans files in the contestant directory. These examples satisfy the constraints for the specified test cases.