Problem: This is the easy version of the problem. The difference between the versions is in the number of possible operations that can be made. You can make hacks if and only if you solved both versions of the problem.

You are given a binary table of size n × m. This table consists of symbols 0 and 1.

You can make such operation: select 3 different cells that belong to one 2 × 2 square and change the symbols in these cells (change 0 to 1 and 1 to 0).

Your task is to make all symbols in the table equal to 0. You are allowed to make at most 3nm operations. You don't need to minimize the number of operations.

It can be proved that it is always possible.

Input

The first line contains a single integer t (1 ≤ t ≤ 5000) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains two integers n, m (2 ≤ n, m ≤ 100).

Each of the next n lines contains a binary string of length m, describing the symbols of the next row of the table.

It is guaranteed that the sum of nm for all test cases does not exceed 20000.

Output

For each test case print the integer k (0 ≤ k ≤ 3nm) — the number of operations.

In the each of the next k lines print 6 integers x_1, y_1, x_2, y_2, x_3, y_3 (1 ≤ x_1, x_2, x_3 ≤ n, 1 ≤ y_1, y_2, y_3 ≤ m) describing the next operation. This operation will be made with three cells (x_1, y_1), (x_2, y_2), (x_3, y_3). These three cells should be different. These three cells should belong into some 2 × 2 square.

Example

Input


5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101


Output


1
1 1 2 1 2 2
2 
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2 
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2 
1 4 1 5 2 5 
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

Note

In the first test case, it is possible to make only one operation with cells (1, 1), (2, 1), (2, 2). After that, all symbols will be equal to 0.

In the second test case:

  * operation with cells (2, 1), (3, 1), (3, 2). After it the table will be: 
    
          
    011  
    001  
    000  
    

  * operation with cells (1, 2), (1, 3), (2, 3). After it the table will be: 
    
          
    000  
    000  
    000  
    




In the fifth test case:

  * operation with cells (1, 3), (2, 2), (2, 3). After it the table will be: 
    
          
    010  
    110  
    

  * operation with cells (1, 2), (2, 1), (2, 2). After it the table will be: 
    
          
    000  
    000  
    

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long n, m;
  cin >> n >> m;
  long long arr[n][m];
  for (long long i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (long long j = 0; j < m; j++) {
      arr[i][j] = (long long)s[j] - 48;
    }
  }
  long long ops = 0;
  vector<long long> out;
  for (long long i = 0; i < n - 1; i += 2) {
    for (long long j = 0; j < m - 1; j += 2) {
      long long count = 0;
      if (arr[i][j] == 1) {
        count++;
      }
      if (arr[i][j + 1] == 1) {
        count++;
      }
      if (arr[i + 1][j] == 1) {
        count++;
      }
      if (arr[i + 1][j + 1] == 1) {
        count++;
      }
      if (count == 4) {
        ops += 1;
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        arr[i][j] = 0;
        arr[i][j + 1] = 0;
        arr[i + 1][j + 1] = 0;
        count = 1;
      }
      if (count == 2) {
        ops += 1;
        if (arr[i][j] == 1 && arr[i][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          arr[i][j] = 0;
          arr[i + 1][j + 1] = 1;
          arr[i + 1][j] = 1;
        } else if (arr[i + 1][j] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i][j + 1] = 1;
          arr[i + 1][j + 1] = 0;
        } else if (arr[i][j] == 1 && arr[i + 1][j] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          arr[i][j] = 0;
          arr[i][j + 1] = 1;
          arr[i + 1][j + 1] = 1;
        } else if (arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i + 1][j + 1] = 0;
          arr[i + 1][j] = 1;
        } else if (arr[i][j] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          arr[i][j] = 0;
          arr[i][j + 1] = 1;
          arr[i + 1][j] = 1;
        } else {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i][j + 1] = 0;
          arr[i + 1][j + 1] = 1;
        }
        count = 3;
      }
      if (count == 3) {
        ops += 1;
        if (arr[i][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1 && arr[i][j + 1] == 1 &&
                   arr[i + 1][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1 && arr[i][j] == 1 &&
                   arr[i + 1][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
        }
      }
      if (count == 1) {
        ops += 3;
        if (arr[i][j] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
        } else if (arr[i][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j + 1);
        }
      }
      arr[i][j] = 0;
      arr[i + 1][j + 1] = 0;
      arr[i][j + 1] = 0;
      arr[i + 1][j] = 0;
    }
  }
  if (n % 2 != 0) {
    long long i = n - 2;
    for (long long j = 0; j < m - 1; j++) {
      long long count = 0;
      if (arr[i][j] == 1) {
        count++;
      }
      if (arr[i][j + 1] == 1) {
        count++;
      }
      if (arr[i + 1][j] == 1) {
        count++;
      }
      if (arr[i + 1][j + 1] == 1) {
        count++;
      }
      if (count == 4) {
        ops += 1;
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        arr[i][j] = 0;
        arr[i][j + 1] = 0;
        arr[i + 1][j + 1] = 0;
        count = 1;
      }
      if (count == 2) {
        ops += 1;
        if (arr[i][j] == 1 && arr[i][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          arr[i][j] = 0;
          arr[i + 1][j + 1] = 1;
          arr[i + 1][j] = 1;
        } else if (arr[i + 1][j] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i][j + 1] = 1;
          arr[i + 1][j + 1] = 0;
        } else if (arr[i][j] == 1 && arr[i + 1][j] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          arr[i][j] = 0;
          arr[i][j + 1] = 1;
          arr[i + 1][j + 1] = 1;
        } else if (arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i + 1][j + 1] = 0;
          arr[i + 1][j] = 1;
        } else if (arr[i][j] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          arr[i][j] = 0;
          arr[i][j + 1] = 1;
          arr[i + 1][j] = 1;
        } else {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i][j + 1] = 0;
          arr[i + 1][j + 1] = 1;
        }
        count = 3;
      }
      if (count == 3) {
        ops += 1;
        if (arr[i][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1 && arr[i][j + 1] == 1 &&
                   arr[i + 1][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1 && arr[i][j] == 1 &&
                   arr[i + 1][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
        }
      }
      if (count == 1) {
        ops += 3;
        if (arr[i][j] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
        } else if (arr[i][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j + 1);
        }
      }
      arr[i][j] = 0;
      arr[i + 1][j + 1] = 0;
      arr[i][j + 1] = 0;
      arr[i + 1][j] = 0;
    }
  }
  if (m % 2 != 0) {
    long long j = m - 2;
    for (long long i = 0; i < n - 1; i++) {
      long long count = 0;
      if (arr[i][j] == 1) {
        count++;
      }
      if (arr[i][j + 1] == 1) {
        count++;
      }
      if (arr[i + 1][j] == 1) {
        count++;
      }
      if (arr[i + 1][j + 1] == 1) {
        count++;
      }
      if (count == 4) {
        ops += 1;
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        arr[i][j] = 0;
        arr[i][j + 1] = 0;
        arr[i + 1][j + 1] = 0;
        count = 1;
      }
      if (count == 2) {
        ops += 1;
        if (arr[i][j] == 1 && arr[i][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          arr[i][j] = 0;
          arr[i + 1][j + 1] = 1;
          arr[i + 1][j] = 1;
        } else if (arr[i + 1][j] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i][j + 1] = 1;
          arr[i + 1][j + 1] = 0;
        } else if (arr[i][j] == 1 && arr[i + 1][j] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          arr[i][j] = 0;
          arr[i][j + 1] = 1;
          arr[i + 1][j + 1] = 1;
        } else if (arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i + 1][j + 1] = 0;
          arr[i + 1][j] = 1;
        } else if (arr[i][j] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          arr[i][j] = 0;
          arr[i][j + 1] = 1;
          arr[i + 1][j] = 1;
        } else {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          arr[i][j] = 1;
          arr[i][j + 1] = 0;
          arr[i + 1][j + 1] = 1;
        }
        count = 3;
      }
      if (count == 3) {
        ops += 1;
        if (arr[i][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1 && arr[i][j + 1] == 1 &&
                   arr[i + 1][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1 && arr[i][j] == 1 &&
                   arr[i + 1][j + 1] == 1) {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else {
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
        }
      }
      if (count == 1) {
        ops += 3;
        if (arr[i][j] == 1) {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
        } else if (arr[i][j + 1] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else if (arr[i + 1][j] == 1) {
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
        } else {
          out.push_back(i);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j);
          out.push_back(i + 1);
          out.push_back(j + 1);
          out.push_back(i);
          out.push_back(j + 1);
        }
      }
      arr[i][j] = 0;
      arr[i + 1][j + 1] = 0;
      arr[i][j + 1] = 0;
      arr[i + 1][j] = 0;
    }
  }
  if (n % 2 != 0 && m % 2 != 0) {
    long long i = n - 2;
    long long j = m - 2;
    long long count = 0;
    if (arr[i][j] == 1) {
      count++;
    }
    if (arr[i][j + 1] == 1) {
      count++;
    }
    if (arr[i + 1][j] == 1) {
      count++;
    }
    if (arr[i + 1][j + 1] == 1) {
      count++;
    }
    if (count == 4) {
      ops += 1;
      out.push_back(i);
      out.push_back(j);
      out.push_back(i);
      out.push_back(j + 1);
      out.push_back(i + 1);
      out.push_back(j + 1);
      arr[i][j] = 0;
      arr[i][j + 1] = 0;
      arr[i + 1][j + 1] = 0;
      count = 1;
    }
    if (count == 2) {
      ops += 1;
      if (arr[i][j] == 1 && arr[i][j + 1] == 1) {
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i);
        out.push_back(j);
        arr[i][j] = 0;
        arr[i + 1][j + 1] = 1;
        arr[i + 1][j] = 1;
      } else if (arr[i + 1][j] == 1 && arr[i + 1][j + 1] == 1) {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        arr[i][j] = 1;
        arr[i][j + 1] = 1;
        arr[i + 1][j + 1] = 0;
      } else if (arr[i][j] == 1 && arr[i + 1][j] == 1) {
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i);
        out.push_back(j);
        arr[i][j] = 0;
        arr[i][j + 1] = 1;
        arr[i + 1][j + 1] = 1;
      } else if (arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j + 1);
        arr[i][j] = 1;
        arr[i + 1][j + 1] = 0;
        arr[i + 1][j] = 1;
      } else if (arr[i][j] == 1 && arr[i + 1][j + 1] == 1) {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        arr[i][j] = 0;
        arr[i][j + 1] = 1;
        arr[i + 1][j] = 1;
      } else {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        arr[i][j] = 1;
        arr[i][j + 1] = 0;
        arr[i + 1][j + 1] = 1;
      }
      count = 3;
    }
    if (count == 3) {
      ops += 1;
      if (arr[i][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
      } else if (arr[i + 1][j] == 1 && arr[i][j + 1] == 1 &&
                 arr[i + 1][j + 1] == 1) {
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
      } else if (arr[i + 1][j] == 1 && arr[i][j] == 1 &&
                 arr[i + 1][j + 1] == 1) {
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j + 1);
      } else {
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
      }
    }
    if (count == 1) {
      ops += 3;
      if (arr[i][j] == 1) {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
      } else if (arr[i][j + 1] == 1) {
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
      } else if (arr[i + 1][j] == 1) {
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j + 1);
      } else {
        out.push_back(i);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j);
        out.push_back(i + 1);
        out.push_back(j + 1);
        out.push_back(i);
        out.push_back(j + 1);
      }
    }
    arr[i][j] = 0;
    arr[i + 1][j + 1] = 0;
    arr[i][j + 1] = 0;
    arr[i + 1][j] = 0;
  }
  cout << ops << "\n";
  for (long long i = 0; i < out.size(); i += 6) {
    cout << out[i] + 1 << " " << out[i + 1] + 1 << " " << out[i + 2] + 1 << " "
         << out[i + 3] + 1 << " " << out[i + 4] + 1 << " " << out[i + 5] + 1
         << "\n";
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) solve();
  return 0;
}