Given a grid with \(n\) rows and \(m\) columns, each cell may contain nothing or a cross consisting of three dotted segments and one solid segment. Let's denote the cell located on the \(i\)-th row and the \(j\)-th column by \((i, j)\).

When you click on a cross, it will rotate 90 degrees clockwise, thus changing the direction the solid segment points to. Your goal is to click on some crosses in some proper order so that the solid segment of every cross points upwards.

But beware, this task is harder than you think it may be. After the rotation of a cross in \((i,j)\) ends, the cross \((i',j')\) pointed by the solid segment of \((i,j)\) will also begin to rotate 90 degrees clockwise, and after the rotation of \((i',j')\) ends, another cross may be triggered if pointed by the solid segment of \((i',j')\)... This chain reaction comes to an end only when the solid segment of the previously-rotated cross points to an empty cell or points out of the map.

To help you understand, please check the following pictures showing a chain reaction on a grid with \(n = m = 3\) step by step.

This is the initial state before the chain reaction. |
After clicking, (1, 1) rotates 90 degrees clockwise |

(1, 2) is activated and rotates 90 degrees clockwise. |
(1, 3) is activated and rotates 90 degrees clockwise. |

(1, 2) is activated again and rotates. |
(2, 2) is activated and rotates 90 degrees clockwise. |

As (2, 3) is an empty cell, |

Given a grid with \(n\) rows and \(m\) columns, please find out a proper order to click on the crosses so that the solid segment of every cross points upwards. You can perform at most 6000 clicks for each test case.

There are multiple test cases. The first line of the input contains an integer \(T\) (\(1 \le T \le 50\)), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10\)), indicating the size of the grid.

For the following \(n\) lines, the \(i\)-th line contains \(m\) integers \(t_{i,1}, t_{i,2}, \dots, t_{i,m}\) (\(-1 \le t_{i,j} \le 3\)), where \(t_{i,j}\) indicates the initial state of the cross at intersection \((i, j)\).

- If \(t_{i,j} = 0\), the solid segment of the cross in cell \((i,j)\) is initially pointing upwards.
- If \(t_{i,j} = 1\), the solid segment of the cross in cell \((i,j)\) is initially pointing leftwards.
- If \(t_{i,j} = 2\), the solid segment of the cross in cell \((i,j)\) is initially pointing downwards.
- If \(t_{i,j} = 3\), the solid segment of the cross in cell \((i,j)\) is initially pointing rightwards.
- If \(t_{i,j} = -1\), cell \((i,j)\) is an empty cell.

For each test case, first output one line containing one integer \(k\) (\(0 \le k \le 6000\)), indicating the number of clicks. Then \(k\) lines follow. Each line contains two integers \(i, j\) (\(1 \le i \le n, 1 \le j \le m\)) separated by a space, indicating that you click on the cross in cell \((i, j)\).

If there's no way to make the solid segment of every cross point upwards in 6000 clicks, just output "-1" (without quotes) instead.

提交代码