题目描述

一个 $n \times n$ 的矩形，单元格 $(x, y)$ 表示其位于第 $x$ 行第 $y$ 列。科学家发明了一种新型网络系统，这种新型网络系统中可以建立多个子网，每个子网需要建立一个 $1$ 号基站 $(x_1, y_1)$ 和 $2$ 号基站 $(x_2, y_2)$，该子网可以覆盖以 $(x_1, y_1)$ 和 $(x_2, y_2)$ 为顶点的矩形区域（矩形区域的四条边必须平行于行和列）。

$1$ 号基站只能在标记为 $1$ 的单元格中建立，$2$ 号基站只能在矩形的四个顶点单元格（标记为 $2$）中建立。

不同的子网覆盖区域之间可以相互重叠。

同一个单元格可以建立多个基站。

问最少需要建立多少个子网能将矩形中所有的单元格覆盖。

输入格式

第 $1$ 行 $1$ 个整数 $T$ ，表示有 $T$ 组测试数据，每一组数据输入如下:

第 $1$ 行 $2$ 个整数 $n, m$ ，表示矩形的行数和列数。

接下来 $n$ 行描述了矩形中单元格的属性。

第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ ，用空格分隔。如果 $a_{i, j}$ 为 $0$，表示单元格 $(i, j)$ 不能 建立任何基站。如果 $a_{i, j}$ 为 $1$ ，表示单元格 $(i, j)$ 可以建立 $1$ 号基站。如果 $a_{i, j}$ 为 $2$，表示单 元格 $(i, j)$ 可以建立 $2$ 号基站。

输出格式

输出 $T$ 行，每行 $1$ 个整数，表示如果能将所有单元格覆盖，需要建立的最少子网数量。

样例输入输出

1
4 4
2 0 0 2
0 1 0 0
0 0 1 0
2 0 0 2

4

1
4 3
2 0 2
1 0 0
1 0 0
2 0 2

2

说明/提示

【样例 #1 解释】

样例 $1$ 中，最少需要建立 $4$ 个子网，其中一种情况如下：

• 建立子网 $1$，选择 $1$ 号方格 $(2, 2)$ 和 $2$ 号方格 $(1, 1)$；
• 建立子网 $2$，选择 $1$ 号方格 $(3, 3)$ 和 $2$ 号方格 $(1, 4)$；
• 建立子网 $3$，选择 $1$ 号方格 $(3, 3)$ 和 $2$ 号方格 $(4, 1)$；
• 建立子网 $4$，选择 $1$ 号方格 $(3, 3)$ 和 $2$ 号方格 $(4, 4)$。

【样例 #2 解释】

样例 $2$ 中，最少需要建立 $2$ 个子网，其中一种情况如下：

• 建立子网 $1$，选择 $1$ 号方格 $(2, 1)$ 和 $2$ 号方格 $(1, 3)$；
• 建立子网 $2$，选择 $1$ 号方格 $(3, 1)$ 和 $2$ 号方格 $(4, 3)$。

数据范围

• 对于 $30\%$ 的数据，$3 \le n,m \le 50$；
• 对于 $100\%$ 的数据，$1 \le T \le 10$，$3 \le n, m \le 100$。