There is a rectangular field divided into r × c square cells.
Potatoes grow on all cells of the field. You have a potato harvester and want to harvest all of them. A potato harvester is basically a large car equipped with mechanical spades and other stuff necessary to get the potatoes from the soil to the back of the car. The driver has a switch that turns the mechanical spades on and off.
The harvester operates in passes. In each pass it traverses either a single row or a single column of the field, starting at one border and ending at the opposite one. The capacity of the harvester is limited: in each pass it can only harvest at most d cells. These can be any of the cells it passes through. In this task your goal will be to produce a harvesting schedule that uses the smallest number of passes.
In practice there is one more factor: harvester drivers are bad at following complicated instructions. Harvesting contiguous segments is much simpler than repeatedly turning the spades off and on again at the right places. The difficulty of a given pass can be measured as the number of times the driver has to flip the switch during the pass. In other words, the difficulty is twice the number of contiguous segments of cells harvested in that pass. (Note: The driver must harvest each cell exactly once. It is not allowed to leave the spades on while the harvester passes over already harvested cells, as this damages the soil.)
The difficulty of a schedule is the difficulty of the most complicated pass it contains, i.e., the maximum over all difficulties of individual passes.
Problem specification
You will be given the dimensions r and c and the capacity d. For the easy data set H1 your task is to produce any harvesting schedule with the smallest number of passes. For the hard data set H2 your task is to produce any harvesting schedule that solves the easy data set and additionally has the smallest possible difficulty (out of all such schedules).
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case is given as a single line with three integers: r, c, and d.
Each test case in the easy data set has r,c ≤ 12. Each test case in the hard data set has r,c ≤ 400.
Output specification
For each test case, output r rows, each containing c space-separated positive integers. These represent the harvesting schedule. More precisely, each integer gives the number of the pass in which the particular cell is harvested. (Additional whitespace is OK as long as the number of tokens in your output is correct.)
Example
The first test case: The cells are harvested in rows. The second test case: We first do one pass in each column and then three passes in the last row. The output shows a schedule that is shortest but does not have the smallest possible difficulty – to fix that, swap the 8 with one of the 7s.