题目描述

小 L 建立了一个都是彩色房屋的社区！

今天他在社区散步时注意到某些颜色重复过多，因此他决定制定城市规划方案来优化房屋颜色分布。

社区被建模为 $N \times M$ 的网格，每个单元格代表一栋房屋。要求任意两栋曼哈顿距离小于 $D$ 的房屋必须涂不同颜色（曼哈顿距离：$|i_1-i_2| + |j_1-j_2|$）。

他希望最小化使用的颜色数量（因为订购多种颜料成本高昂）。请帮助设计一个着色方案，使得：

1. 使用的颜色数量 $K$ 最少
2. 输出具体着色方案（颜色用 $1$ 到 $K$ 的整数表示）

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含三个整数 $N$、$M$ 和 $D$，分别表示网格的行数、列数和最小曼哈顿距离限制。

输出格式

对于每个测试用例，首先输出一个整数 $K$ 表示所需的最少颜色数量。

接着输出 $N$ 行，每行包含 $M$ 个用空格分隔的整数，表示网格中每个位置的颜色编号（必须为 1 到 $K$ 之间的整数）。相邻测试用例的输出之间不需要空行。

样例输入

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 \leq T \leq 100$，$1 \leq N, M \leq 500$，$1 \leq D \leq 1000$。

所有测试用例的 $N$ 总和不超过 $500$。

所有测试用例的 $M$ 总和不超过 $500$。