//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#include <cassert>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second



using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = 250 * 500 + 42, inf = 1000111222;

struct dsu {
    int p_or_sz[max_n];

    void init(int n) {
        for (int i = 0; i < n; ++i) {
            p_or_sz[i] = -1;
        }
    }

    int find_set(int v) {
        if (p_or_sz[v] < 0) {
            return v;
        }
        return p_or_sz[v] = find_set(p_or_sz[v]);
    }

    bool union_set(int v1, int v2) {
        v1 = find_set(v1);
        v2 = find_set(v2);
        if (v1 == v2) {
            return false;
        }
        if (-p_or_sz[v1] > -p_or_sz[v2]) {
            swap(v1, v2);
        }
        p_or_sz[v2] += p_or_sz[v1];
        p_or_sz[v1] = v2;
        return true;
    }
};

vector<int> g[max_n];

bool used[max_n];

vector<int> visited;

array<int, 4> tot_state, state[max_n]; //up, down, left, right

void dfs(int v) {
    for(int i = 0; i < 4; i++) tot_state[i] += state[v][i];
    visited.pb(v);
    used[v] = true;
    for(auto& to : g[v])
        if(!used[to])
            dfs(to);
}

namespace barik
{
    int tin[max_n];
    int fup[max_n];
    int tout[max_n];
    int curt;
    vector<int> cur;
    vector<int> g2[2*max_n];
    int bicomps;

    array<int, 4> total_down[2*max_n];


    void dfs_barik(int v,int p)
    {
        cur.pb(v);
        tin[v]=fup[v]=++curt;
        for (auto to:g[v]){
            if (to==p){
                continue;
            }
            if (!tin[to]){
                dfs_barik(to,v);
                if (tin[v]<=fup[to]){
                    g2[v].pb(max_n+bicomps);
                    while (g2[max_n+bicomps].empty() || g2[max_n+bicomps].back()!=to){
                        g2[max_n+bicomps].pb(cur.back());
                        cur.pop_back();
                    }
                    bicomps++;
                }
                fup[v]=min(fup[v],fup[to]);
            }
            else{
                fup[v]=min(fup[v],tin[to]);
            }
        }
    }
    void dfs_barik_tree_g2(int v,int p,bool& is_ok)
    {
        if (v<max_n){
            total_down[v]=state[v];
        }
        else{
            total_down[v]={0,0,0,0};
        }
        for (auto to:g2[v]){
            if (to==p){
                continue;
            }
            dfs_barik_tree_g2(to,v,is_ok);
            bool flag=1;
            for (int j=0;j<4;j++){
                flag&=(total_down[to][j]!=0);
            }
            if (flag){
                is_ok=0;
            }
            for (int j=0;j<4;j++){
                total_down[v][j]+=total_down[to][j];
            }
        }

        if (p!=-1){
            bool flag=1;
            for (int j=0;j<4;j++){
                flag&=(tot_state[j]!=total_down[v][j]);
            }
            if (flag){
                is_ok=0;
            }
        }
    }

    void solve(const vector<int>& visited,bool& is_ok)
    {
        DEBUG{
            for (auto i:visited){
                cerr<<i<<"    ";
                cerr<<"with values (";
                for (int j=0;j<4;j++){
                    cerr<<" "<<state[i][j]<<" ";
                }
                cerr<<" ) ";
                cerr<<"  ->   ";
                for (auto j:g[i]){
                    cerr<<j<<" ";
                }
                cerr<<"\n";
            }
        };
        {
            dfs_barik(visited[0],-1);
            dfs_barik_tree_g2(visited[0],-1,is_ok);
        }

        for (auto i:visited){
            tin[i]=0;
            fup[i]=0;
            tout[i]=0;
        }
        curt=0;
        cur.clear();
        for (auto i:visited){
            g2[i].clear();
        }
        for (int i=max_n;i<=max_n+bicomps+1;i++){
            g2[i].clear();
        }
        bicomps=0;
    }
}

void solve() {
    for(int i = 0; i < max_n; i++) g[i].clear();
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i = 0; i < n; i++) cin >> s[i];
    int cind = 0;
    int in_row = m * 2;
    vector<pair<int, int> > edges;
    auto is_white = [&](int x) {
        return s[x / in_row][x % in_row] == '0';
    };
    auto add_edge = [&](int a, int b) {
        if(is_white(a) && is_white(b)) {
            edges.pb({a, b});
            g[a].pb(b);
            g[b].pb(a);
        }
    };
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if((i + j) % 2 == 0) { // --
                add_edge(cind, cind + 1);
                if(j - 1 >= 0) {
                    add_edge(cind - 1, cind);
                    add_edge(cind - 2, cind);
                }
                if(i - 1 >= 0) {
                    add_edge(cind, cind - in_row + 1);
                    add_edge(cind + 1, cind - in_row + 1);
                }
            } else { // |
                add_edge(cind, cind + 1);
                if(j - 1 >= 0) {
                    add_edge(cind - 1, cind);
                    add_edge(cind - 1, cind + 1);
                }
                if(i - 1 >= 0) {
                    add_edge(cind, cind - in_row);
                    add_edge(cind, cind - in_row + 1);
                }
            }
            cind += 2;
        }
    }
    //todo test edges
    cind = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            array<int, 4> cind0 = {0, 0, 0, 0}, cind1 = {0, 0, 0, 0};
            if((i + j) % 2 == 0) { // --
                if(i == 0) {
                    cind0[0] = 1;
                    cind1[0] = 1;
                }
                if(j == 0) {
                    cind0[2] = 1;
                }
                if(i == n - 1) {
                    cind0[1] = 1;
                    cind1[1] = 1;
                }
                if(j == m - 1) {
                    cind1[3] = 1;
                }
            } else { // |
                if(i == 0) {
                    cind0[0] = 1;
                }
                if(j == 0) {
                    cind0[2] = 1;
                    cind1[2] = 1;
                }
                if(i == n - 1) {
                    cind1[1] = 1;
                }
                if(j == m - 1) {
                    cind0[3] = 1;
                    cind1[3] = 1;
                }
            }
            state[cind + 0] = cind0;
            state[cind + 1] = cind1;
            cind += 2;
        }
    }
    //todo test states
    for(int i = 0; i < max_n; i++) used[i] = false;
    for(int i = 0; i < n * in_row; i++)
        if(!used[i] && is_white(i)) {
            visited.clear();
            tot_state = {0, 0, 0, 0};
            dfs(i);
            if(tot_state[0] && tot_state[1] && tot_state[2] && tot_state[3]) {
                bool is_ok = true;
                int amv = len(visited);
                vector<bool> is_good(max_n);
                for(auto& x : visited) is_good[x] = true;
                vector<pair<int, int> > nedges;
                for(auto& x : edges)
                    if(is_good[x.fi] && is_good[x.se])
                        nedges.pb(x);
                edges.swap(nedges);
                for(int j = 0; j < max_n; j++) g[j].clear();
                for(auto& x : edges) {
                    g[x.fi].pb(x.se);
                    g[x.se].pb(x.fi);
                }
                barik::solve(visited,is_ok);
                //todo
                if(is_ok) cout << amv << '\n';
                else cout << "NO MINIMAL CORRIDOR\n";
                return;
            }
        }
    cout << "NO MINIMAL CORRIDOR\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/