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  
    
#include <bits/stdc++.h>
#include <x86intrin.h>
#include <ext/pb_ds/assoc_container.hpp>

// Defines
#define F               first
#define S               second
#define endl            "\n"
#define NO              "NO\n"
#define YES             "YES\n"
#define elif            else if
#define mp              make_pair
#define pp              pop_back
#define pb              push_back
#define int             long long
#define ld              long double
#define lb              lower_bound
#define ub              upper_bound
#define pii             pair<int,int>
#define sz(x)           int32_t(x.size())
#define all(x)          x.begin(),x.end()
#define rall(x)         x.rbegin(),x.rend()
#define pll             pair<long long,long long>
#define FOR(i,a,b)      for(int i = (a); i <= (b); i++)
#define REV(i,a,b)      for(int i = (a); i >= (b); i--)
#define precal(x)       fixed << setprecision(x)
#define IOS             ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define FILE            freopen("max.in", "r", stdin);freopen("max.out", "w", stdout)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// Constants
const int LOG = 23;
const int N = 400+23;
const int MOD = 1e9+7;
const int B = 318;
const long long INF = 2e18+1703;
const int dx[10] = {0,0,1,-1,0};
const int dy[10] = {0,1,0,0,-1};

//  [x-1,y-1] [x-1,y] [x-1,y+1];
//  [x,y-1]   [x, y]  [x,y+1];
//  [x+1,y-1] [x+1,y] [x+1,y+1];

// Functions
long long bp(long long a,long long b){
    long long res = 1;
    while(b > 0){
        if(b&1)res = (res*a)%MOD, b--;
        a = (a*a)%MOD, b >>= 1;
    }
    return res;
}
bool bit(long long x,int p){
    return (x >> p)&1;
}
long long gcd(long long a,long long b){
    return __gcd(a,b);
}
long long lcm(long long a,long long b){
    return (a*b)/__gcd(a,b);
}
bool prime(long long x){
    if((!(x&1) && x > 2) || (x <= 1))return 0;
    for(long long d = 3; d*d <= x; d += 2){
        if(!(x%d))return 0;
    }
    return 1;
}

/*
    CHECK LIMITS FOR -> N, MOD, INF ;)

    Don't forget this:
    Greedy, Dp, Tree, Dsu, Binary search, Bitmask, Brute Force, Data structures, Sort, Graphs, Games tactics, Graph matchings, Number theory, Shortest paths

    Bit operations:
    1) 1^1 = 0, 0^0 = 0, 1^0 = 1, 0^1 = 0
    2) 1&1 = 1, 0&0 = 0, 1&0 = 0, 0&1 = 0
    3) 1|1 = 1, 0|0 = 0, 1|0 = 1, 0|1 = 1

    Tricks to solve:
    1) Reverse the problem
    2) If it equation try to remake in a better way
    3) Draw some tests and solve them by drawing
    4) Maybe there is a regularity?
    5) Try from the opposite to prove the greediness
    6) You can use prefix, suffix arrays and solve with them
    7) Offline or online solutions?
*/

int n,m;
char a[N][N];
int pre[N][N],ver[N][N],hor[N][N],x[N],y[N];
int check(int i1,int i2,int j1,int j2){
    int res = pre[i2-1][j2-1]-(pre[i1][j2-1]+pre[i2-1][j1])+pre[i1][j1];
    res += (j2-j1-1)-(hor[i1][j2-1]-hor[i1][j1]);
    res += (j2-j1-1)-(hor[i2][j2-1]-hor[i2][j1]);
    res += (i2-i1-1)-(ver[i2-1][j1]-ver[i1][j1]);
    res += (i2-i1-1)-(ver[i2-1][j2]-ver[i1][j2]);
    return res;
}
void solve(){
    cin >> n >> m;
    FOR(i,1,n){
        FOR(j,1,m){
            cin >> a[i][j];
            pre[i][j] = pre[i][j-1]+(a[i][j] != '0');
            hor[i][j] = hor[i][j-1]+(a[i][j] != '0');
            ver[i][j] = ver[i-1][j]+(a[i][j] != '0');
        }
        FOR(j,1,m){
            pre[i][j] += pre[i-1][j];
        }
    }
    int ans = INF;
    FOR(i1,1,n){
        FOR(j1,1,m){
            FOR(i2,i1+4,n){
                if(j1+3 <= m){
                    int j2 = j1+3;
                    ans = min(ans,check(i1,i2,j1,j2));
                }
            }
        }
    }
    FOR(i,1,m){
        FOR(j,i+3,m){
            int sum = 0,mn = INF;
            FOR(k,1,n){
                int cnt1 = (j-i-1)-(hor[k][j-1]-hor[k][i]);
                int cnt0 = (a[k][i] == '0')+pre[k][j-1]-pre[k][i]+(a[k][j] == '0');
                sum += cnt0;
                x[k] = cnt1;
                y[k] = sum;
                if(i >= 5){
                    mn = min(mn,x[i-4]-y[i-4]);
                    ans = min(ans,cnt1+sum-cnt0+mn);
                }
            }
        }
    }
    cout << ans << endl;
}
int32_t main(){
    IOS;
    int test_cases = 1; cin >> test_cases;
    while(test_cases--){
        solve();
    }
    return 0;
}
