← 返回题目列表

Codeforces · 1701/A

A. 草地

中文机器翻译题面 查看原题

有一个大小为 $$$2 \times 2$$$ 的字段。该字段的每个单元格可以包含草或空。如果单元格 $$$(i, j)$$$ 包含草,则值 $$$a_{i, j}$$$ 为 $$$1$$$,否则为 $$$0$$$。

一招可以选择一行一列,将这一行这一列的草全部砍掉。换句话说,您选择行 $$$x$$$ 和列 $$$y$$$,然后在所有单元格 $$$a_{x, i}$$$ 和所有单元格 $$$a_{i, y}$$$ 中为从 $$$1$$$ 到 $$$2$$$ 的所有 $$$i$$$ 割草。当你从一个单元格中割掉草后,它就会变成空的(即它的值被 $$$0$$$ 取代)。

你的任务是找到在场地的所有非空单元格中割草所需的最少移动次数(即将所有 $$$a_{i, j}$$$ 为零)。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 16$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例由两行组成,每行包含两个整数。第 $$$i$$$ 行中的第 $$$j$$$ 整数是 $$$a_{i, j}$$$。如果 $$$a_{i, j} = 0$$$ 则单元格 $$$(i, j)$$$ 为空,如果 $$$a_{i, j} = 1$$$ 则单元格 $$$(i, j)$$$ 包含草。

输出

对于每个测试用例,打印一个整数 - 在相应的测试用例中割草场所有非空单元格中的草所需的最小移动次数(即将所有 $$$a_{i, j}$$$ 为零)。

示例

输入 #1

3
0 0
0 0
1 0
0 1
1 1
1 1

输出 #1

0
1
2