You have exactly \(3\) phones and \(3\) chargers. You wish to charge all the phones as fast as possible. To do this, you must assign every phone to a charger such that the total wait time is minimized. Each charger can be used to charge at most \(1\) phone, so you cannot move phones between chargers, or assign \(2\) phones to a charger.

Input Specification

The first line contains a single integer \(T\) (\(1\leq T \leq 10\)), the number of test cases to follow. Each test cases comprises \(3\) lines, each corresponding to a phone. Each of these lines contains \(3\) integers in the inclusive range from \(1\) to \(100\). The \(i\)th of these is the time it takes to charge the corresponding phone using the \(i\)th charger.

Output Specification

For each test case output a single line containing a single integer, the minimum possible time to charge every phone.

Sample Input

2
3 2 1
1 2 3
2 1 2
3 2 1
1 2 3
2 3 1

Sample Output

1
2