The Marinero neighborhood of Fontán, in La Coruña, is known for its colorful houses. Luis and Darío took a walk through this neighborhood and noticed that some colors were repeating too much. Therefore, they decided to create an urban planning plan to distribute the colors of the houses in the best possible way.
They have modeled the neighborhood as a $$$N \times M$$$ grid, where each cell contains a house. They want any two houses that are less than distance $$$D$$$ apart to be painted in different colors. Due to the nature of the problem, they have chosen the Manhattan distance; that is, the distance between cell $$$(i_1, j_1)$$$ and cell $$$(i_2, j_2)$$$ is $$$|i_1 - i_2| + |j_1 - j_2|$$$.
The mayor has asked them to minimize the number of colors needed to paint the neighborhood, as ordering many types of different paint can be very expensive. However, Darío and Luis do not know how to minimize the number of colors used to paint their grid. Can you help them achieve an $$$N \times M$$$ grid such that the number of colors needed is minimized?
The first line of the input contains the number of cases $$$T$$$.
For each case, there will be a line of input with three integers $$$N$$$, $$$M$$$, and $$$D$$$, the dimensions of the grid and the minimum distance that must be between two houses for them to have the same color.
For each case, an integer should be printed on the first line indicating the minimum number of colors needed.
The following $$$N$$$ lines must contain $$$M$$$ integers. The $$$j$$$-th integer of the $$$i$$$-th row represents the color of the cell $$$(i, j)$$$.
Each value of each cell must be an integer between 1 and the minimum number of colors. If the value of the cell $$$(i, j)$$$ is $$$k$$$, the house in cell $$$(i, j)$$$ must be painted the $$$k$$$-th color.
3 3 3 1 2 4 1000 3 3 3
1 1 1 1 1 1 1 1 1 1 8 1 2 3 4 5 6 7 8 5 1 2 3 3 4 5 5 1 2
$$$1 \le T \le 100$$$.
$$$1 \le N, M \le 500$$$.
The sum of $$$N$$$ and the sum of $$$M$$$ for all cases is at most $$$500$$$.
$$$1 \le D \le 1000$$$.
