E. Combination Lock
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are faced with a combination lock that consists of an $$$n$$$ by $$$m$$$ grid of dials. A $$$k$$$-dial is a dial that can display values $$$0, 1, \cdots k-1$$$. A $$$k$$$-dial currently displaying value $$$v$$$ can be incremented to make it display value $$$(v + 1)\mod k$$$.

This particular lock consists of $$$3$$$-dials and $$$5$$$-dials in a checkerboard arrangement, with the top left dial being a $$$3$$$-dial. In a single move, you can increment a dial and all of its horizontal and vertical neighbors.

For example, here is one possible sequence of moves on a grid with $$$n=3$$$, $$$m=4$$$ (where $$$3$$$-dials are gray and $$$5$$$-dials are white):

Initially, all of the dials are displaying $$$0$$$. You remember what positions the dials must be in for the lock to open, but you forgot the combination of moves to reach it. Find a sequence of moves that sets all dials to the correct positions. You do not need to minimize the number of moves, but you can use no more than $$$20nm$$$ moves.

It can be shown that such a solution always exists.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$) — the number of rows and columns in the grid, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers describing the $$$i$$$-th row of the combination. The $$$j$$$-th of these is $$$a_{ij}$$$, the desired position of the dial at position $$$(i, j)$$$. If $$$i+j$$$ is even, $$$0 \le a_{ij} \lt 3$$$. Otherwise, $$$0 \le a_{ij} \lt 5$$$.

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$10^4$$$.

Output

The first line of output for each test case should contain a single integer $$$k$$$ ($$$0 \le k \le 20nm$$$) — the number of moves you will perform.

The next $$$k$$$ lines of output should each contain integers $$$i$$$ and $$$j$$$, indicating that the next move will be performed at position $$$(i, j)$$$.

If there are multiple solutions, print any.

Example
Input
5
3 3
0 1 0
1 1 1
0 1 0
2 3
0 0 0
0 0 0
3 5
0 1 2 3 0
0 1 4 0 2
0 0 1 2 0
1 1
1
2 2
2 4
4 2
Output
1
2 2
0
4
1 3
2 4
2 4
2 3
1
1 1
4
1 1
1 1
2 2
2 2
Note

Here is the move used in the first sample case:

In the second sample case, the lock is already in the target position, so no moves are needed.