Alice 正在玩一款手机游戏，游戏的目标是通过放置防御塔来保护基地免受僵尸的侵害。游戏中的基地可以表示为一个大小为 $N \times M$ 的矩阵。Alice 可以在矩阵边界内的任意单元格中放置防御塔。如果在任意 $K \times K$ 的正方形中都至少有一个防御塔，则认为基地得到了保护。请帮助 Alice 找到一种能够保护基地的防御塔放置方案。由于她刚刚开始玩游戏，没有多少金币，因此在所有可能的放置方案中，输出防御塔数量最少的方案对应的防御塔数量。

实现细节

您需要实现以下函数：

int32 solve(int32 N, int32 M, int32 K)

输入参数 $N, M, K$ 的含义如上所述，该函数必须返回上述指定的答案。

注意：在程序单次运行中，该函数可能会被调用多次。

数据范围

• $1 \le N, M \le 50$。
• $1 \le K \le \min(N, M)$。
• 在单次运行中，该函数最多被调用 $50\,000$ 次。

子任务

1. 子任务 1（8 分）：$K = 1$。
2. 子任务 2（27 分）：$K = 2$。
3. 子任务 3（31 分）：$N = M$ 且 $K$ 整除 $N$。
4. 子任务 4（34 分）：无附加限制。

样例

在以下图片中，防御塔用红色圆圈表示。

考虑以下调用 solve(5, 5, 2)。在这种情况下（$N = M = 5, K = 2$），我们创建以下排列：

考虑以下调用 solve(7, 8, 3)。在这种情况下（$N = 7, M = 8, K = 3$），我们创建以下排列：

考虑以下调用 solve(4, 4, 1)。在这种情况下（$N = M = 4, K = 1$），我们创建以下排列：

样例评测程序

样例评测程序首先读取 $T$，即调用函数 solve 的次数，然后读取 $T$ 行，每行包含调用 solve 所需的 $N, M, K$ 值。接着，它在不同的行中输出 $T$ 个 solve 的返回值。样例中的输入和输出文件均使用此格式。