CF 3

#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;
}

void slv(){
    int 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 i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if (i == 0 && j == 0 && i == n - 1 && j == m -1 || i == 0 && j == m - 1 || i == n - 1 && j == 0){
                continue;
            }
            vector <pii> can;
            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()){
                continue;
            }
            if (can[can.size() - 1].first == 0){
                continue;
            }
            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);
            }
        }
    }
    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();
    }
}