题目描述

有一个 $2 \times 2$ 的田地。每个格子里可能有草，也可能是空的。若格子 $(i, j)$ 有草，则 $a_{i, j} = 1$，否则 $a_{i, j} = 0$。

每次操作，你可以选择一行和一列，并割掉该行和该列所有格子里的草。也就是说，你选择第 $x$ 行和第 $y$ 列，然后将所有 $a_{x, i}$ 和 $a_{i, y}$（$i$ 从 $1$ 到 $2$）中的草全部割掉。割完后，该格子变为空（即其值变为 $0$）。

你的任务是求出最少需要多少次操作，才能将田地里所有有草的格子都变为空（即所有 $a_{i, j}$ 都变为 $0$）。

你需要回答 $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)$ 有草。

输出格式

对于每组测试用例，输出一个整数，表示将田地里所有有草的格子都变为空所需的最少操作次数。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

0
1
2