#include<bits/stdc++.h>
#define vi vector
#define pb push_back
#define ar array 
using namespace std ;
void solve(){
  int n,m ;cin >> n >> m ;
  vi<string>a(n) ; 
  for(string &x:a) 
    cin >> x ; 
  vi<vi<ar<int,2>>>ans ;
  function<void(int,int)> fix=[&](int i,int j){
    vi<ar<int,2>>o,z ;
    for(int r=0;r<2;r++)
      for(int c=0;c<2;c++){
        if(a[i+r][j+c]=='1')
          o.pb({i+r,j+c}) ;
        else 
          z.pb({i+r,j+c}) ;
      }
    if(o.size()==0)
      return  ;
    a[o[0][0]][o[0][1]]='0' ;
    if(o.size()==1 || o.size()==2){
      a[z[0][0]][z[0][1]]='1' ;
      a[z[1][0]][z[1][1]]='1' ;
      ans.pb({o[0],z[0],z[1]}) ;
    }
    if(o.size()==3 || o.size()==4){
      a[o[1][0]][o[1][1]]='0' ;
      a[o[2][0]][o[2][1]]='0' ;
      ans.pb({o[0],o[1],o[2]}) ;
    }
    fix(i,j) ;
    return ;
  } ;
  for(int i=0;i<n-1;i++)
    for(int j=0;j<m-1;j++)
      fix(i,j)  ;
  cout << ans.size() << '\n' ;
  for(auto x:ans){
    for(auto y:x)
      cout << y[0]+1 << " " << y[1]+1 << " " ;
    cout << '\n' ;
  }
}
signed main(){
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}

#include <algorithm>
#include <iostream>

using namespace std;

#define all(x) (x).begin(), (x).end()
int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        /// Input
        int n, m;
        cin >> n >> m;
        
        string s[n];
        for (int i = 0; i < n; ++i)
            cin >> s[i];
            


        /// Calculation
        int cnt = 0;
        for (int i = 0; i < n; ++i)           /// For each '1' appear
            cnt += 3 * count(all(s[i]), '1'); /// We use 3 operations to turn off it
                                              /// These operations are independent
 
        /// Output the result
        cout << cnt << '\n';
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (s[i][j] == '1')
                {
                    int cx = i + 1; /// +1 because we use 0-based loop
                    int cy = j + 1; /// +1 because we use 0-based loop
                    int px = (cx < n) ? cx + 1 : cx - 1; /// Next row
                    int py = (cy < m) ? cy + 1 : cy - 1; /// Next col

                    /// Notice that these operation are independent
                    /// They wont affect others cells, just turn off [i][j]

                    cout << px << ' ' << cy << ' ';  ///  X O  |  + +  |  O X
                    cout << cx << ' ' << py << ' ';  ///  O O  |  + _  |  X O
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 1 -> 2

                    cout << px << ' ' << cy << ' ';  ///  O X  |  + _  |  X X
                    cout << px << ' ' << py << ' ';  ///  X O  |  + +  |  O X
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 2 -> 3

                    cout << cx << ' ' << py << ' ';  ///  X X  |  + +  |  O O
                    cout << px << ' ' << py << ' ';  ///  O X  |  _ +  |  O O
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 3 -> 0
                }
            }
        }
    }
    return 0;
}

$$$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$$$

For $$$N$$$ ones in table, it need exact $$$3 \times N$$$ operations

For every $$$N \cdot M$$$ table, it need averagely $$$\frac{3N}{2}$$$ operations

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define all(x) (x).begin(), (x).end()

/// Each line of the answer
struct node { 
    int a, b, c, d, e, f; 
    node (int a, int b, int c, int d, int e, int f)
    :       a(a),  b(b),  c(c),  d(d),  e(e),  f(f) {}
};

vector<node> res;
vector<vector<int> > a;
void flip(const node &x)
{
    a[x.a][x.b] ^= 1;
    a[x.c][x.d] ^= 1;
    a[x.e][x.f] ^= 1;
    res.push_back(x);
}

int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        /// Input
        int n, m;
        cin >> n >> m;
        
        a.assign(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i)
        {
            string s;
            cin >> s;
            
            for (int j = 1; j <= m; ++j)
                a[i][j] = s[j - 1] - '0'; /// Convert string to array
        }
        
        res.clear();
        
        /// Odd row elimination
        if (n & 1)
        {
            for (int j = 1; j <= m; ++j) /// Eliminate 2x1 cells by once
            {
                int p = (j == m) ? (j - 1) : (j + 1);
                if (a[n][j]) flip(node(n-0,j   ,   n-1,j   ,   n-1,p));
            }
            --n; /// <- Last row eliminated
        }
        
        /// Odd column elimination
        if (m & 1)
        {
            for (int i = 1; i <= n; ++i) /// Eliminate 1x2 cells by once
            {
                int p = (i == n) ? (i - 1) : (i + 1);
                if (a[i][m]) flip(node(i,m-0   ,   i,m-1   ,   p,m-1));
            }
            --m; /// <- last col eliminated
        }
        
        /// Eliminate 2x2 cells by once
        for (int i = 1; i <= n; i += 2)
        {
            for (int j = 1; j <= m; j += 2)
            {
                int x = 0, y = 0, z = 0, t = 0;
                if (a[i + 0][j + 0]) x ^= 0, y ^= 1, z ^= 1, t ^= 1;
                if (a[i + 1][j + 0]) x ^= 1, y ^= 0, z ^= 1, t ^= 1;
                if (a[i + 0][j + 1]) x ^= 1, y ^= 1, z ^= 0, t ^= 1;
                if (a[i + 1][j + 1]) x ^= 1, y ^= 1, z ^= 1, t ^= 0;
            
                if (x) flip(node(i+1,j+0   ,   i+0,j+1   ,   i+1,j+1));
                if (y) flip(node(i+0,j+0   ,   i+0,j+1   ,   i+1,j+1));
                if (z) flip(node(i+0,j+0   ,   i+1,j+0   ,   i+1,j+1));
                if (t) flip(node(i+0,j+0   ,   i+1,j+0   ,   i+0,j+1));
            }
        }
        
        /// Output the result
        cout << res.size() << '\n';
        for (const node &x : res)
        {
            cout << x.a << ' ' << x.b << ' ';
            cout << x.c << ' ' << x.d << ' ';
            cout << x.e << ' ' << x.f << '\n';
        }
    }
    return 0;
}

$$$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$$$

For $$$S$$$ ones in table, it need maximumly $$$min(N \cdot M, 3 \times S)$$$ operations

For every $$$N \cdot M$$$ table, it need averagely $$$\frac{N}{2}$$$ operations and maximumly $$$N * M$$$ operations

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define all(x) (x).begin(), (x).end()

/// Each line of the answer
struct node { 
    int a, b, c, d, e, f; 
    node (int a, int b, int c, int d, int e, int f)
    :       a(a),  b(b),  c(c),  d(d),  e(e),  f(f) {}
};

vector<node> res;
vector<vector<int> > a;
void flip(const node &x)
{
    a[x.a][x.b] ^= 1;
    a[x.c][x.d] ^= 1;
    a[x.e][x.f] ^= 1;
    res.push_back(x);
}

int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        /// Input
        int n, m;
        cin >> n >> m;

        /// Initalization
        res.clear();
        a.assign(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i)
        {
            string s;
            cin >> s;
            
            for (int j = 1; j <= m; ++j)
                a[i][j] = s[j - 1] - '0'; /// Convert string to array
        }
        


        /// Odd column elimination
        if (m & 1)
        {
            for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once
            {
                if (a[i0][m] == 0) continue;
                int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1);
//                if (a[i1][m]) flip(node(i0,m-0   ,   i1,m-0   ,   i0,m-1));
//                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));

                if (a[i1][m]) /// Greedy one more step
                {
                    int p = a[i1][m-1] ? i1 : i0; /// Select the one with one
                    flip(node(i0,m-0   ,   i1,m-0   ,   p,m-1));
                }
                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));
            }
            --m; /// <- Last col eliminated
        }
        


        /// Row Elimination: n * m -> 2 * m remaining
        while (n > 2)
        {
            for (int j0 = 1; j0 <= m; ++j0) /// Eliminate 2x1 cells by once
            {
                if (a[n][j0] == 0) continue;
                int j1 = (j0 == m) ? (j0 - 1) : (j0 + 1);
//                if (a[n][j1]) flip(node(n-0,j0   ,   n-0,j1   ,   n-1,j0));
//                else          flip(node(n-0,j0   ,   n-1,j0   ,   n-1,j1));

                if (a[n][j1])  /// Greedy one more step
                {
                    int p = a[n-1][j1] ? j1 : j0; /// Select the one with one
                    flip(node(n-0,j0   ,   n-0,j1   ,   n-1,p));
                }
                else          flip(node(n-0,j0   ,   n-1,j0   ,   n-1,j1));
            }
            --n; /// <- Last row eliminated
        }
        


        /// Col Elimination: 2 * m -> 2 * 2 remaining
        while (m > 2)
        {
            for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once
            {
                if (a[i0][m] == 0) continue;
                int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1);
//                if (a[i1][m]) flip(node(i0,m-0   ,   i1,m-0   ,   i0,m-1));
//                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));

                if (a[i1][m]) /// Greedy one more step
                {
                    int p = a[i1][m-1] ? i1 : i0; /// Select the one with one
                    flip(node(i0,m-0   ,   i1,m-0   ,   p,m-1));
                }
                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));
            }
            --m; /// <- Last col eliminated
        }
        


        /// Cells Elimination: 2 * 2 -> 0 * 0 remaining - Using modular equations
        int x = 0, y = 0, z = 0, t = 0;
        if (a[1][1]) x ^= 0, y ^= 1, z ^= 1, t ^= 1;
        if (a[2][1]) x ^= 1, y ^= 0, z ^= 1, t ^= 1;
        if (a[1][2]) x ^= 1, y ^= 1, z ^= 0, t ^= 1;
        if (a[2][2]) x ^= 1, y ^= 1, z ^= 1, t ^= 0;

        if (x) flip(node(2,1   ,   1,2   ,   2,2));
        if (y) flip(node(1,1   ,   1,2   ,   2,2));
        if (z) flip(node(1,1   ,   2,1   ,   2,2));
        if (t) flip(node(1,1   ,   2,1   ,   1,2));
     


        /// Output the result
        cout << res.size() << '\n';
        for (const node &x : res)
        {
            cout << x.a << ' ' << x.b << ' ';
            cout << x.c << ' ' << x.d << ' ';
            cout << x.e << ' ' << x.f << '\n';
        }
    }
    return 0;
}

$$$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$$$

For every $$$N \cdot M$$$ table, it need averagely $$$\frac{N}{2}$$$ operations and maximumly $$$min(N \cdot M, \lceil \frac{n + 1}{2} \rceil + \lceil \frac{m(n - 2)}{2} \rceil + (m - 2) + 3)$$$ operations