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
注意
第一个测试用例中,最终的传送门是这样的: