A. Grass Field
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a field of size $$$2 \times 2$$$. Each cell of this field can either contain grass or be empty. The value $$$a_{i, j}$$$ is $$$1$$$ if the cell $$$(i, j)$$$ contains grass, or $$$0$$$ otherwise.

In one move, you can choose one row and one column and cut all the grass in this row and this column. In other words, you choose the row $$$x$$$ and the column $$$y$$$, then you cut the grass in all cells $$$a_{x, i}$$$ and all cells $$$a_{i, y}$$$ for all $$$i$$$ from $$$1$$$ to $$$2$$$. After you cut the grass from a cell, it becomes empty (i. e. its value is replaced by $$$0$$$).

Your task is to find the minimum number of moves required to cut the grass in all non-empty cells of the field (i. e. make all $$$a_{i, j}$$$ zeros).

You have to answer $$$t$$$ independent test cases.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 16$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The test case consists of two lines, each of these lines contains two integers. The $$$j$$$-th integer in the $$$i$$$-th row is $$$a_{i, j}$$$. If $$$a_{i, j} = 0$$$ then the cell $$$(i, j)$$$ is empty, and if $$$a_{i, j} = 1$$$ the cell $$$(i, j)$$$ contains grass.

Output

For each test case, print one integer — the minimum number of moves required to cut the grass in all non-empty cells of the field (i. e. make all $$$a_{i, j}$$$ zeros) in the corresponding test case.

Example
Input
3
0 0
0 0
1 0
0 1
1 1
1 1
Output
0
1
2