CF1580A.Portal

CQXYM found a rectangle $A$ of size $n \times m$. There are $n$ rows and $m$ columns of blocks. Each block of the rectangle is an obsidian block or empty. CQXYM can change an obsidian block to an empty block or an empty block to an obsidian block in one operation.

A rectangle $M$ size of $a \times b$ is called a portal if and only if it satisfies the following conditions:

• $a \geq 5,b \geq 4$.
• For all $1 \lt x \lt a$, blocks $M_{x,1}$ and $M_{x,b}$ are obsidian blocks.
• For all $1 \lt x \lt b$, blocks $M_{1,x}$ and $M_{a,x}$ are obsidian blocks.
• For all $1 \lt x \lt a,1 \lt y \lt b$, block $M_{x,y}$ is an empty block.
• $M_{1, 1}, M_{1, b}, M_{a, 1}, M_{a, b}$ can be any type.

Note that the there must be $a$ rows and $b$ columns, not $b$ rows and $a$ columns.

Note that corners can be any type

CQXYM wants to know the minimum number of operations he needs to make at least one sub-rectangle a portal.

CQXYM 发现了一个大小为 $n \times m$ 的矩形 $A$。该矩形共有 $n$ 行和 $m$ 列方块。每个方块要么是黑曜石方块，要么是空方块。CQXYM 每次操作可以将一个黑曜石方块变为一个空方块，或将一个空方块变为一个黑曜石方块。

一个大小为 $a \times b$ 的矩形 $M$ 被称为“传送门”（portal），当且仅当它满足以下条件：

• $a \geq 5,\ b \geq 4$。
• 对所有 $1 \lt x \lt a$，方块 $M_{x,1}$ 和 $M_{x,b}$ 均为黑曜石方块。
• 对所有 $1 \lt x \lt b$，方块 $M_{1,x}$ 和 $M_{a,x}$ 均为黑曜石方块。
• 对所有 $1 \lt x \lt a,\ 1 \lt y \lt b$，方块 $M_{x,y}$ 均为空方块。
• 方块 $M_{1, 1},\ M_{1, b},\ M_{a, 1},\ M_{a, b}$ 可以是任意类型（黑曜石或空）。

注意：该矩形必须有 $a$ 行和 $b$ 列，而非 $b$ 行和 $a$ 列。

注意：四个角（即上述第 5 条中提到的方块）可以是任意类型。

CQXYM 想知道：使原矩形中至少存在一个子矩形是传送门所需的最少操作次数。

The first line contains an integer $t$ ($t \geq 1$), which is the number of test cases.

For each test case, the first line contains two integers $n$ and $m$ ($5 \le n \le 400$, $4 \le m \le 400$).

Then $n$ lines follow, each line contains $m$ characters $0$ or $1$. If the $j$-th character of $i$-th line is $0$, block $A_{i,j}$ is an empty block. Otherwise, block $A_{i,j}$ is an obsidian block.

It is guaranteed that the sum of $n$ over all test cases does not exceed $400$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $400$.

第一行包含一个整数 $t$（$t \geq 1$），表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$（$5 \le n \le 400$，$4 \le m \le 400$）。

接下来是 $n$ 行，每行包含 $m$ 个字符，每个字符为 $0$ 或 $1$。若第 $i$ 行的第 $j$ 个字符为 $0$，则方块 $A_{i,j}$ 为空方块；否则，方块 $A_{i,j}$ 为黑曜石方块。

保证所有测试用例的 $n$ 之和不超过 $400$。

保证所有测试用例的 $m$ 之和不超过 $400$。

Output $t$ answers, and each answer in a line.

输出 $t$ 个答案，每个答案占一行。

In the first test case, the final portal is like this:

1110
1001
1001
1001
0111

在第一个测试用例中，最终的传送门如下所示：

1110
1001
1001
1001
0111