Controlling traffic lights on crossing roads is one of the most essential applications of scheduling algorithms. Elaborating on those details will be a long story. In short, for this task, you will control the traffic lights to resolve a already-happened traffic jam.

The following figure shows a typical example of a crossing road in a Right-hand Traffic (RHT, meaning that drivers keep to the right side of the road). If we do not consider cases where drivers turn around, there are 12 directions: N->E, N->S, N->W, E->S, E->W, E->N, S->W, S->N, S->E, W->N, W->E and W->S.



We have the situation here that there is already a traffic jam. The number of cars driving in the 12 directions are already known respectively. Each car needs 1 second to pass the crossing road to reach the destination. We assume there is no more traffic jam after they manage to drive through the crossing road. There will be no more cars entering this jam either.

Your task is to assign a appropriate traffic light for each second, so that the traffic jam is resolved (all the cars successfully pass the crossing roads) as quickly as possible. The assignment should also guarantee no potential collision between cars. The following figure show a valid example.



Here is a bad case. It is illegal because there can be two collisions as marked in the figure, but we allow that two cars run into the S direction simultaneously and we do not penalize for this.

The first line of input is a number T (), which is the number of test cases.

For each test case, there will be 4 lines, representing a matrix. Each line is 4 integers separated by space, representing one row of the matrix.

The j-th integer on i-th line  (, ) denotes number of cars attempting to drive from the i-th direction to j-th direction, where the i-th direction means N, E, S, W for i=1,2,3,4 respectively. For example,  corresponds to S->E.

For each test case, output one number, which is the minumum number of seconds to resolve the traffic jam.

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

1
17

For example 1, there are only 3 cars running from the same direction, and they can go simultaneously.

For example 2, here is what could happen during the 17 seconds.

1. N->W, W->S, E->W
2. E->N, E->W, S->W, W->S
3. N->W, E->S, E->W
4. S->E, E->S, E->W
5. W->S, E->S, W->N
6. E->S, N->W, W->N
7. W->S, E->S, W->N
8. W->S, N->E, S->W
9. N->W, N->E, S->W
10. W->S, N->E, S->W
11. S->E, E->W, W->E
12. E->W, W->S, W->E
13. S->E, E->W, W->E
14. S->E, E->W, W->E
15. S->E, E->W, W->E
16. S->E, N->S, S->N
17. S->N, S->W, W->S