题目描述
小 L 建立了一个都是彩色房屋的社区！
今天他在社区散步时注意到某些颜色重复过多，因此他决定制定城市规划方案来优化房屋颜色分布。
社区被建模为 $N \times M$ 的网格，每个单元格代表一栋房屋。要求任意两栋曼哈顿距离小于 $D$ 的房屋必须涂不同颜色（曼哈顿距离：$|i_1-i_2| + |j_1-j_2|$）。
他希望最小化使用的颜色数量（因为订购多种颜料成本高昂）。请帮助设计一个着色方案，使得：
- 使用的颜色数量 $K$ 最少
- 输出具体着色方案（颜色用 $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$。
| 子任务 | 分值 | 限制条件 |
|---|---|---|
| $1$ | $8$ | $D=2$ |
| $2$ | $4$ | $N=1$ |
| $3$ | $16$ | $D < \min(N,M)$ |
| $4$ | $19$ | $D < \max(N,M)$ |
| $5$ | $24$ | $D > \max(N,M)$ |
| $6$ | $15$ | $N=M$ |
| $7$ | $14$ | 无特殊限制 |