F. Flos
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Flowers may eventually wither, but the shapes they once formed can still be preserved on paper.

A botanist wishes to recreate a garden with as many flowers as possible on an $$$n \times m$$$ grid. Every cell of the grid must belong to exactly one flower. To represent a garden containing $$$k$$$ flowers, each cell is assigned an integer from $$$1$$$ to $$$k$$$, where a cell labeled $$$i$$$ belongs to the $$$i$$$-th flower.

Each of the $$$k$$$ flowers must occupy at least two cells. Moreover, for each flower, all cells belonging to it must be 4-connected. In other words, one must be able to travel between any two cells of the flower by moving only between side-adjacent cells belonging to the same flower.

The flowers in this garden must also be intertwined so that the grid cannot be separated into two parts by a single horizontal or vertical cut along grid lines. More precisely:

  • For every pair of consecutive rows, there must be at least one flower that occupies cells both above and below the line between them.
  • For every pair of consecutive columns, there must be at least one flower that occupies cells both to the left and to the right of the line between them.

Find the maximum possible number of flowers and construct a corresponding grid.

Input

The first line contains an integer $$$t$$$, denoting the number of test cases.

Each of the next $$$t$$$ lines contains two integers $$$n$$$ and $$$m$$$, denoting the number of rows and columns in that test case, respectively.

  • $$$1 \leq t \leq 10\,000$$$
  • $$$1 \leq n, m \leq 500$$$
  • $$$n \times m \geq 2$$$
  • The sum of $$$n \times m$$$ over all test cases does not exceed $$$500^2$$$.
Output

For each test case, first output an integer $$$k$$$, the maximum possible number of flowers.

Then, output $$$n$$$ lines, each containing $$$m$$$ integers. The integer in row $$$r$$$ and column $$$c$$$ must be the label of the flower occupying that cell. Every label from $$$1$$$ to $$$k$$$ must appear, and the resulting grid must satisfy all the conditions described above.

If there are multiple valid grids, output any one of them.

Example
Input
3
1 3
2 4
3 5
Output
1
1 1 1
3
1 1 3 3
1 2 2 2
7
1 1 2 2 3
6 7 7 7 3
6 5 5 4 4
Note

The following figure illustrates the output for the third test case in the sample. Cells with the same color and label belong to the same flower.

For example, flower $$$7$$$ occupies three consecutive cells in the second row. The figure also shows that every horizontal or vertical line between consecutive rows or columns is crossed by at least one flower. It can be shown that no valid garden can contain $$$8$$$ or more flowers.