Little L has built a community of colorful houses!

Today, while walking through the community, he noticed that some colors were used too frequently, so he decided to create an urban planning scheme to optimize the distribution of house colors.

The community is modeled as an $N \times M$ grid, where each cell represents a house. It is required that any two houses with a Manhattan distance less than $D$ must be painted different colors (Manhattan distance: $|i_1-i_2| + |j_1-j_2|$).

He wants to minimize the number of colors used (as ordering many types of paint is expensive). Please help design a coloring scheme such that:

1. The number of colors $K$ used is minimized.
2. The specific coloring scheme is output (colors are represented by integers from $1$ to $K$).

Input

The first line of the input contains an integer $T$, representing the number of test cases. The first line of each test case contains three integers $N$, $M$, and $D$, representing the number of rows, the number of columns, and the minimum Manhattan distance constraint, respectively.

Output

For each test case, first output an integer $K$ representing the minimum number of colors required.

Then, output $N$ lines, each containing $M$ space-separated integers, representing the color number for each position in the grid (must be an integer between $1$ and $K$). No empty lines are required between the outputs of adjacent test cases.

Examples

Input 1

3
3 3 1
2 4 1000
3 3 3

Output 1

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

Constraints

For all data, it is guaranteed that $1 \leq T \leq 100$, $1 \leq N, M \leq 500$, and $1 \leq D \leq 1000$.

The sum of $N$ over all test cases does not exceed $500$.

The sum of $M$ over all test cases does not exceed $500$.