您从神秘来源收到了 $$$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$$$。