[Solution] Grass Field solution codeforces

Grass Field solution codeforces – There is a field of size 2×22×2. Each cell of this field can either contain grass or be empty. The value 𝑎𝑖,𝑗ai,j is 11 if the cell (𝑖,𝑗)(i,j) contains grass, or 00 otherwise.

Table of Contents

[Solution] Grass Field solution codeforces

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 𝑎𝑥,𝑖ax,i and all cells 𝑎𝑖,𝑦ai,y for all 𝑖i from 11 to 22. After you cut the grass from a cell, it becomes empty (i. e. its value is replaced by 00).

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 𝑎𝑖,𝑗ai,j zeros).

You have to answer 𝑡t independent test cases.

Input

The first line of the input contains one integer 𝑡t (1𝑡161≤t≤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 𝑎𝑖,𝑗ai,j. If 𝑎𝑖,𝑗=0ai,j=0 then the cell (𝑖,𝑗)(i,j) is empty, and if 𝑎𝑖,𝑗=1ai,j=1 the cell (𝑖,𝑗)(i,j) contains grass.

[Solution] Grass Field solution codeforces

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 𝑎𝑖,𝑗ai,j zeros) in the corresponding test case.

Example
input

Copy
3
0 0
0 0
1 0
0 1
1 1
1 1
output

Copy
0
1
2

 

For Solution

Click Here

Leave a Comment