题目描述

你有一块 $r\times c$ 的田地，每个格子里都有一个土豆。你需要收割田地中所有的土豆。

每天，你可以驾驶一辆收集车采收土豆。你可以选择一行或一列，让收集车沿着这一行或这一列行驶，并选择收集经过格子中的部分土豆。

每一天至多收集 $d$ 个土豆。当天被收集的土豆会在所选的行或列上形成若干段连续线段；形成多少段线段，就意味着当天需要开启或重新启动多少次机器。

请构造一种收割方案，使得：

1. 收割完所有土豆所需的天数最少；
2. 在天数最少的前提下，机器开启或重启次数的总和最少。

输入格式

第一行包含一个正整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含三个正整数 $r,c,d$。

输出格式

对于每组测试数据，输出 $r$ 行，每行包含 $c$ 个整数。

第 $i$ 行第 $j$ 个整数表示格子 $(i,j)$ 中的土豆被收割的日期。

样例输入

2
2 9 5
3 5 2

样例输出

1 1 1 1 1 2 2 2 2
3 3 3 3 3 4 4 4 4
1 2 3 4 5
1 2 3 4 5
6 6 7 8 7

样例解释

第一组样例一共需要 $4$ 天，每天收割的土豆都只形成一段连续线段。

第二组样例一共需要 $8$ 天，第 $7$ 天收割的土豆分成两段。

注意： 原题面说明，第二组样例的正确结果应将右下角附近的 7 和 8 交换。也就是说，最后一行应为：

6 6 7 7 8

数据范围

• 对于 $50\%$ 的数据：$1\le r,c\le 12$，$T\le 10$；
• 对于 $100\%$ 的数据：$1\le r,c\le 400$，$T\le 100$，且所有测试数据的 $rc$ 之和不超过 $5\times 10^5$。