Welcome to ZOJ
148 - The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - I
Domino Tiling

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

Chiaki has an n × m rectangular chessboard. She would like to tile this board with dominoes, where a domino is a 2 × 1 rectangle, such that:

  • all the squares of the board are covered but no dominoes overlap or lie partially off the board.
  • there must be no points where corners of four different dominoes meet.

The figure below shows some forbidden configurations:

The figure below shows two valid tilings of 4 × 4 chessboard:

You also need to number the dominoes of chessboard so that no two dominoes have the same number. You can use the number from 1 to n × m.


There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the size of the rectangular chessboard.

It is guaranteed that the sum of n × m over all test cases does not exceed 2 × 106.


For each test case, output a valid chessboard described above. A valid chessboard consists of n lines and each line contains m integers. Each integer in the output should represent the id of a domino. The grids sharing the same id belong to the same domino.

If there is no solution, output "Impossible!" (without the quotes) instead.

Sample Input

1 1
4 3
4 4

Sample Output

1 1 2
3 4 2
3 4 5
6 6 5
1 1 2 2
3 4 4 5
3 6 6 5
7 7 8 8

Submit    Status