CF C

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvs(vector <string>  v){
    for (auto a: v){
        cout<<a<<"\n";
    }
}

void cvp(vector <pii> a){
    for (auto p: a){
        cout<<p.first<<' '<<p.second<<"\n";
    }
    cout<<"\n";
}

int t=1,n,m;
vector <vector <int> > v;

bool sh=0;

void d1(int x, int y){
    v[x][y]=0;
    v[x+1][y]=0;
    v[x][y+1]=0;
}







int f1(int x, int y){
    int r=0;
    if(v[x][y]==1)r++;
    if(v[x+1][y]==1)r++;
    if(v[x][y+1]==1)r++;
    return r;
}

void d2(int x, int y){
    v[x][y] = 0;
    v[x+1][y]=0;
    v[x][y-1]=0;
}

int f2(int x, int y){
    int r=0;
    if(v[x][y]==1)r++;
    if(v[x+1][y]==1)r++;
    if(v[x][y-1]==1)r++;
    return r;
}

void d3(int x, int y){
    v[x][y]=0;
    v[x-1][y]=0;
    v[x][y+1]=0;
}

int f3(int x, int y){
    int r=0;
    if(v[x][y]==1)r++;
    if(v[x-1][y]==1)r++;
    if(v[x][y+1]==1)r++;
    return r;
}


void d4(int x, int y){
    v[x][y]=0;
    v[x][y-1]=0;
    v[x-1][y]=0;
}


int f4(int x, int y){
    int r=0;
    if(v[x][y]==1)r++;
    if( v[x][y-1]==1)r++;
    if(v[x-1][y]==1)r++;
    return r;
}

const int inf = 2e9;

bool cmp(pii a, pii b){//{nmb of 1, id oper}
    return a.first < b.first || a.first == b.first && a.second > b.second;
}


vector <pii> can;
int ans=0;

void op(int i, int j){
    can.clear();
    if (i + 1 < n && j + 1 < m){
        can.push_back({f1(i,j),1});
    }
    if (i + 1 < n && j - 1 > 0){
        can.push_back({f2(i,j),2});
    }
    if (i - 1 > 0 && j + 1 < m){
        can.push_back({f3(i,j),3});
    }
    if (i - 1 > 0 && j - 1 > 0){
        can.push_back({f4(i,j),4});
    }
    if (can.empty()){
        return;
    }
    sort(can.begin(), can.end(), cmp);
    if (can[can.size() - 1].first == 0){
        return;
    }
    ans++;
    pii p = can[0];
    if (p.second == 1){
        d1(i,j);
    }
    else if (p.second == 2){
        d2(i,j);
    }
    else if (p.second == 3){
        d3(i,j);
    }
    else{
        d4(i,j);
    }
}

void slv(){
    ans=0;


    if (f4(1,1) > 0){
        ans++;
        d4(1,1);
    }
    if (f3(1,m-2) > 0){
        d3(1,m-1);
        ans++;
    }
    if (f2(n-2, 1) > 0){
        d2(n-2, 1);
        ans++;
    }
    if (f1(n-2, m-2) > 0){
        d1(n-2, m-2);
        ans++;
    }

    for (int j = 2; j < m - 2;++j){
        op(0,j);
    }
    for (int j = 2; j < m - 2;++j){
        op(n-1,j);
    }
    for (int i=2;i<n-2;++i){
        op(i, 0);
    }
    for (int i = 2; i < n - 2; ++i){
        op(i, m-1);
    }

    for (int i = 2; i < n-2; ++i){
        for (int j = 2; j < m-2; ++j){
            op(i,j);
        }
    }
    if (v[0][0] == 1){
        ans++;
        d1(0, 0);
    }
    if (v[0][m-1] == 1){
        ans++;
        d2(0,m-1);
    }
    if (v[n-1][0] == 1){
        ans++;
        d3(n - 1, 0);
    }
    if (v[n-1][m-1] == 1){
        ans++;
        d4(n-1, m-1);
    }
    cout<<ans<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	if (!sh) cin>>t;
	for (int go = 0; go < t; ++go){
        cin>>n>>m;
        string s;
        v.assign(n, vector <int> (m, 0));
        for (int i= 0; i < n; ++i){
            cin>>s;
            for (int j = 0; j < m; ++j){
                v[i][j] = s[j] - '0';
            }
        }
        if (sh){
            cout<<"v\n"; cvv(v);
        }
        slv();
	}
}