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 < x < a$$$, blocks $$$M_{x,1}$$$ and $$$M_{x,b}$$$ are obsidian blocks.  For all $$$1 < x < b$$$, blocks $$$M_{1,x}$$$ and $$$M_{a,x}$$$ are obsidian blocks.  For all $$$1<x<a,1<y<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 typeCQXYM wants to know the minimum number of operations he needs to make at least one sub-rectangle a portal.
In the first test case, the final portal is like this:11101001100110010111
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$$$.
Output $$$t$$$ answers, and each answer in a line.
import sys
T = int(sys.stdin.readline().strip())

def v(is0, is1, x, y, a, b, flag):
    if flag == 1:
        g = is1
    else:
        g = is0
    return g[a + 1][b + 1] + g[x][y] - g[a + 1][y] - g[x][b + 1]
for t in range(T):
    (n, m) = list(map(int, sys.stdin.readline().strip().split(' ')))
    mat = []
    for i in range(n):
        mat.append(sys.stdin.readline().strip())
    is1 = [[0 for j in range(m + 1)] for i in range(n + 1)]
    is0 = [[0 for j in range(m + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            is1[i][j] = is1[i - 1][j] + is1[i][j - 1] - is1[i - 1][j - 1] + int(mat[i - 1][j - 1] == '1')
            is0[i][j] = is0[i - 1][j] + is0[i][j - 1] - is0[i - 1][j - 1] + int(mat[i - 1][j - 1] == '0')
    res = 16
    for i in range(n):
        for j in range(m):
            for a in range(i + 4, n):
                left = v(is0, is1, i + 1, j, a - 1, j, 0)
                if left >= res:
                    break
                for b in range(j + 3, m):
                    up = v(is0, is1, i, j + 1, i, b - 1, 0)
                    r = left + up
                    if r >= res:
                        break
                    down = v(is0, is1, a, j + 1, a, b - 1, 0)
                    r += down
                    if r >= res:
                        break
                    mid = v(is0, is1, i + 1, j + 1, a - 1, b - 1, 1)
                    r += mid
                    if r >= res:
                        break
                    right = v(is0, is1, i + 1, b, a - 1, b, 0)
                    r += right
                    if r < res:
                        res = r
    print(res)
import sys
for _ in range(int(sys.stdin.readline())):
    (n, m) = [int(i) for i in sys.stdin.readline().split()]
    g = [[int(x) for x in sys.stdin.readline().strip()] for i in range(n)]
    rec = [[0] * (m + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        s = 0
        for j in range(1, m + 1):
            s += g[i - 1][j - 1]
            rec[i][j] = rec[i - 1][j] + s

    def get_rec(a, b, c, d):
        return rec[c][d] + rec[a - 1][b - 1] - rec[c][b - 1] - rec[a - 1][d]

    def get_p(a, b, c, d):
        return 4 - (g[a - 1][b - 1] + g[a - 1][d - 1] + g[c - 1][b - 1] + g[c - 1][d - 1])
    mi = n * m
    for i in range(1, n - 3):
        for j in range(1, m - 2):
            for k in range(i + 4, n + 1):
                left = k - i - 1 - get_rec(i + 1, j, k - 1, j)
                if left >= mi:
                    break
                for l in range(j + 3, m + 1):
                    s = left + l - j - 1 - get_rec(i, j + 1, i, l - 1)
                    s += get_rec(i + 1, j + 1, k - 1, l - 1)
                    s += l - j - 1 - get_rec(k, j + 1, k, l - 1)
                    if s >= mi:
                        break
                    s += k - i - 1 - get_rec(i + 1, l, k - 1, l)
                    if s < mi:
                        mi = s
    sys.stdout.write('%d\n' % mi)
from itertools import accumulate
from sys import stdin, gettrace
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def solve():
    (n, m) = map(int, input().split())
    aa = [[int(a) for a in input()] for _ in range(n)]
    best = 16
    och = [list(accumulate(ar)) for ar in aa]
    for i in range(n):
        for (j, o) in enumerate(och[i]):
            if o > j + 1:
                print('Bad line', aa[i], och[i])
                return
    ocv = [list(accumulate(ac)) for ac in zip(*aa)]
    ob = [list(accumulate(v)) for v in zip(*ocv)]
    for i in range(n - 4):
        for j in range(m - 3):
            for k in range(i + 4, n):
                leftc = k - i - 1 - ocv[j][k - 1] + ocv[j][i]
                if leftc >= best:
                    break
                for l in range(j + 3, m):
                    rightc = k - i - 1 - ocv[l][k - 1] + ocv[l][i]
                    topc = l - j - 1 - och[i][l - 1] + och[i][j]
                    bottomc = l - j - 1 - och[k][l - 1] + och[k][j]
                    ic = ob[k - 1][l - 1] - ob[k - 1][j] - ob[i][l - 1] + ob[i][j]
                    if leftc + topc + ic >= best:
                        break
                    cost = leftc + rightc + topc + bottomc + ic
                    if cost < 0:
                        print('BAD', leftc, rightc, topc, bottomc, ic, cost)
                    best = min(cost, best)
    print(best)

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()