← 返回题目列表

Codeforces · 1580/A

A. 门户

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

CQXYM 找到一个大小为 $$$n \times m$$$ 的矩形 $$$A$$$。块有 $$$n$$$ 行和 $$$m$$$ 列。矩形的每个块都是黑曜石块或空的。 CQXYM 可以在一次操作中将黑曜石块更改为空块或将空块更改为黑曜石块。

一个 $$$M$$$ 大小为 $$$a \times b$$$ 的矩形称为门户当且仅当它满足以下条件时:

- $$$a \geq 5,b \geq 4$$$。
- 对于所有 $$$1 < x < a$$$,块 $$$M_{x,1}$$$ 和 $$$M_{x,b}$$$ 是黑曜石块。
- 对于所有 $$$1 < x < b$$$,块 $$$M_{1,x}$$$ 和 $$$M_{a,x}$$$ 都是黑曜石块。
- 对于所有 $$$1<x<a,1<y<b$$$,块 $$$M_{x,y}$$$ 是一个空块。
- $$$M_{1, 1}、M_{1, b}、M_{a, 1}、M_{a, b}$$$ 可以是任何类型。

请注意,角可以是任何类型

CQXYM 想知道使至少一个子矩形成为门户所需的最少操作数。

输入

第一行包含一个整数$$$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$$$。

输出

输出$$$t$$$答案,并且每个答案在一行中。

示例

输入 #1

1
5 4
1000
0000
0110
0000
0001

输出 #1

12

输入 #2

1
9 9
001010001
101110100
000010011
100000001
101010101
110001111
000001111
111100000
000110000

输出 #2

5

注意

第一个测试用例中,最终的传送门是这样的: