F. Fill T
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

It is the last day of your summer break, and you currently have nothing to do, so you start daydreaming about a problem you had heard once before...

Given a grid with $$$R$$$ rows and $$$C$$$ columns, your task is to cover all the cells with some $$$T$$$-shapes so that each cell is covered by exactly one $$$T$$$-shape. $$$T$$$-shapes must not exceed the boundary of the grid.

More formally, a $$$T$$$-shape in the grid is uniquely determined by six non-negative integers $$$(x,y,u,l,d,r)$$$, where $$$(x,y)$$$ represents the center point of the $$$T$$$-shape, and $$$u$$$, $$$l$$$, $$$d$$$ and $$$r$$$ represent the lengths of the arms of the $$$T$$$-shape in the upward, leftward, downward and rightward directions, respectively.

The six integers must satisfy these conditions:

  • $$$0 \le u,l,d,r$$$, $$$1 \le x \le C$$$, $$$1 \le y \le R$$$
  • $$$1 \le x-l$$$ and $$$x+r \le C$$$
  • $$$1 \le y-u$$$ and $$$y+d \le R$$$
  • Exactly one of the values of $$$u$$$, $$$l$$$, $$$d$$$ and $$$r$$$ must be zero.
Figure F.1: Examples of some $$$T$$$-shapes
Input

Each test contains multiple test cases. The first line contains a single integer $$$t(1\leq t \leq 1,000)$$$ — the number of test cases.

For each test case, there is one line that contains two integers $$$R$$$ and $$$C$$$ $$$(1 \le R,C \le 200)$$$ indicating the size of the grid.

The sum of $$$R \cdot C$$$ over all test cases does not exceed $$$100,000$$$.

Output

For each test case, on the first line, output $$$n$$$ $$$(1 \le n \le \frac{R \cdot C}{4})$$$, the number of $$$T$$$-shapes to cover the grid.

On each of the next $$$n$$$ lines, output six integers $$$x_i, y_i, u_i, l_i, d_i, r_i$$$ separated by a space indicating the $$$i$$$-th $$$T$$$-shape uniquely determined by $$$(x_i, y_i, u_i, l_i, d_i, r_i)$$$ where $$$x_i$$$ and $$$y_i$$$ $$$(1 \le x_i \le C$$$, $$$1 \le y_i \le R)$$$ represents the center point and $$$u_i$$$, $$$l_i$$$, $$$d_i$$$ and $$$r_i$$$ $$$(0 \le u_i,l_i,d_i,r_i)$$$ represent the arms of the $$$T$$$-shape as explained above. If there are multiple valid answers, you can print any of them.

If there is no valid answer, simply output $$$-1$$$ on a single line.

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

The first and the second grid in the example can be filled with $$$T$$$-shapes as follows: