CQXYM found a rectangle A of size n × 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 × b is called a portal if and only if it satisfies the following conditions:

  * a ≥ 5,b ≥ 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 type

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

Input

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

For each test case, the first line contains two integers n and m (5 ≤ n ≤ 400, 4 ≤ m ≤ 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

Output t answers, and each answer in a line.

Examples

Input


1
5 4
1000
0000
0110
0000
0001


Output


12


Input


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


Output


5

Note

In the first test case, the final portal is like this:
    
    
      
    1110  
    1001  
    1001  
    1001  
    0111  
    
import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
from itertools import permutations
import string


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


def get_int():
    return int(input())


def get_ints():
    return list(map(int, input().split(' ')))


def get_int_grid(n):
    return [get_ints() for _ in range(n)]


def get_str():
    return input().strip()


def get_strs():
    return get_str().split(' ')


def flat_list(arr):
    return [item for subarr in arr for item in subarr]


def yes_no(b):
    if b:
        return "YES"
    else:
        return "NO"


def binary_search(good, left, right, delta=1, right_true=False):
    """
    Performs binary search
    ----------
    Parameters
    ----------
    :param good: Function used to perform the binary search
    :param left: Starting value of left limit
    :param right: Starting value of the right limit
    :param delta: Margin of error, defaults value of 1 for integer binary search
    :param right_true: Boolean, for whether the right limit is the true invariant
    :return: Returns the most extremal value interval [left, right] which is good function evaluates to True,
            alternatively returns False if no such value found
    """

    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False


def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p



def inv_mod(a, M):
    '''
    Returns the inverse of a modulo M (prime), uses Fermat's Little Theorem.
    Time complexity: O(log M) - fast exponentiation
    Memory complexity: O(1)
    :param a: number to invert
    :param M: modulo base, must be prime
    :return: returns inverse of a modulo M
    '''
    return pow(a, M - 2, M)


def factorials(n, M):
    '''
    Return an array of kth factorials, modulo M. k in {0, 1, ..., n}
    :param n: maximum factorial to return
    :param M: modulo base, usually (large) prime
    :return: array of kth factorials, modulo M
    '''
    # Initialise an array and 0!
    ret = [0] * (n + 1)
    ret[0] = 1
    # Loop over k in {1, ..., n} and define k!, inductively
    for k in range(1, n + 1):
        ret[k] = (ret[k - 1] * k) % M
    # Return array of factorials
    return ret

M = 10 ** 9 + 7
n_max = 2 * 10 ** 5
facts = factorials(n_max + 1, M)


def solve_a():
    n = get_int()
    return (facts[2 * n] * inv_mod(2, M)) % M


def solve_b():
    n, m, k = get_ints()
    if m < n - 1:
        return "NO"
    if m > (n * (n - 1)) // 2:
        return "NO"
    if k == 0:
        return "NO"
    if k == 1:
        return "NO"
    if k == 2:
        if n == 1:
            return "YES"
        else:
            return "NO"
    if k == 3:
        if m == (n * (n - 1)) // 2:
            return "YES"
        else:
            return "NO"
    else:
        return "YES"


def max_subarray(numbers):
    """Find a contiguous subarray with the largest sum."""
    best_sum = 0  # or: float('-inf')
    best_start = best_end = 0  # or: None
    current_sum = 0
    for current_end, x in enumerate(numbers):
        if current_sum <= 0:
            # Start a new sequence at the current element
            current_start = current_end
            current_sum = x
        else:
            # Extend the existing sequence with the current element
            current_sum += x

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = current_end + 1  # the +1 is to make 'best_end' exclusive

    return best_sum, best_start, best_end


def solve_c():
    n, m = get_ints()
    grid = []
    for _ in range(n):
        grid.append(list(map(int, list(get_str()))))

    pref = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            pref[i][j] = pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + grid[i - 1][j - 1]

    def ones(r1, c1, r2, c2):
        return pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1]

    def zeros(r1, c1, r2, c2):
        return (r2 - r1 + 1) * (c2 - c1 + 1) - ones(r1, c1, r2, c2)

    best = 16

    for r1 in range(n):
        for c1 in range(m):
            b = False
            for r2 in range(r1 + 4, n):
                if b:
                    break
                for c2 in range(c1 + 3, m):
                    swaps = ones(r1 + 1, c1 + 1, r2 - 1, c2 - 1)
                    if swaps >= best:
                        b = True
                        break
                    swaps += zeros(r1, c1 + 1, r1, c2 - 1)
                    swaps += zeros(r1 + 1, c1, r2 - 1, c1)
                    if swaps >= best:
                        b = True
                        break
                    best = min(best, swaps + zeros(r2, c1 + 1, r2, c2 - 1) + zeros(r1 + 1, c2, r2 - 1, c2))
    return best


t = get_int()
for _ in range(t):
    print(solve_c())
