← 返回题目列表

Codeforces · 2002/A

A. 远程着色

中文机器翻译题面 查看原题

您从神秘来源收到了 $$$n\times m$$$ 网格。源代码还给了你一个神奇的正整数常量$$$k$$$。

消息来源告诉你用一些颜色给网格着色,满足以下条件:

- 如果 $$$(x_1,y_1)$$$、$$$(x_2,y_2)$$$ 是两个具有相同颜色的不同单元格,则 $$$\max(|x_1-x_2|,|y_1-y_2|)\ge k$$$。

您不喜欢使用太多颜色。请找出为网格着色所需的最少颜色数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le1000$$$)。测试用例的描述如下。

每个测试用例的唯一行由三个正整数 $$$n$$$、$$$m$$$、$$$k$$$ ($$$1\le n,m,k\le10^4$$$) 组成 - 网格的尺寸和魔法常数。

输出

对于每个测试用例,打印一个整数 - 为网格着色所需的最小颜色数。

示例

输入 #1

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

输出 #1

4
5
12
6
36
8

注意

在第一个测试用例中,最佳结构之一是:

在第二个测试用例中,所有单元格的颜色必须成对不同,因此答案是 $$$5$$$。