题目描述

你从一个神秘的来源那里得到了一个 $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$），分别表示网格的行数、列数和神奇常数。

输出格式

对于每组测试用例，输出一个整数，表示染色该网格所需的最少颜色数。

说明/提示

在第一个测试用例中，一种最优的染色方案如下：

在第二个测试用例中，所有格子的颜色都必须两两不同，所以答案是 $5$。

由 ChatGPT 4.1 翻译

样例

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