A. 距离着色

每次测试的时间限制：1秒
每次测试的内存限制：256兆字节

您从一个神秘来源获得了一个 $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 \le 1000$）。接下来是每个测试用例的描述。

每个测试用例只有一行，包含三个正整数 $n$，$m$，$k$（$1 \le n, m, k \le 10^4$）—— 网格的尺寸和神奇常数。

输出

对于每个测试用例，输出一个整数 —— 为网格着色所需的最少颜色数。

示例

输入

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

输出

4
5
12
6
36
8

注意

在第一个测试用例中，一个最优的着色方案如下所示：（原文附图，此处略）

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