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

The input is read from the file club.in.

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

The output is written to the file club.out. 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.