G. Grid Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two grids of size $$$N \times M$$$, let's call them the target grid and your grid. The cells in both grids can be in one of two states: 'on' or 'off'. Initially, all cells in your grid are 'off', while the target grid has a specific configuration of 'on' and 'off' cells.

Your goal is to make your grid identical to the target grid by using a specific operation. The operation consists of three steps:

  1. Choose a cell at row $$$r$$$ and column $$$c$$$ in your grid.
  2. Flip the state of the chosen cell (if it's 'on', it becomes 'off', and if it's 'off', it becomes 'on').
  3. Simultaneously, every other row $$$i$$$ (where $$$i \ne r$$$) is cyclically shifted one position to the right. For example, a row [c1, c2, c3, c4] would become [c4, c1, c2, c3].

You need to find and print any valid sequence with minimum number of operations that transforms your initially off-state grid into the target grid.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^3)$$$ — the number of test cases. The description of the test cases follows.

The first line of each testcase contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 1000$$$), the number of rows and columns in the grids.

The next $$$N$$$ lines of each testcase each contain a string of $$$M$$$ characters, representing the target grid. The character '1' denotes an 'on' cell, and '0' denotes an 'off' cell.

It's guaranteed that sum of n overall testcases doesn't exceed 1000 and sum of m doesn't exceed 1000.

Output

For each testcase, On the first line, print a single integer $$$K$$$, the minimum number of operations.

On the next $$$K$$$ lines, print two space-separated integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le N$$$, $$$1 \le c \le M$$$), representing the 1-based coordinates of a cell to perform the operation on. The total number of operations must not exceed $$$N \times M$$$.

Example
Input
2
1 1
0
4 2
00
11
01
01
Output
0
4
2 1
2 2
3 1
4 2