codeforces#P2002A. Distanced Coloring

    ID: 34868 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>constructive algorithmsimplementationmath*800

Distanced Coloring

Description

You received an $n\times m$ grid from a mysterious source. The source also gave you a magic positive integer constant $k$.

The source told you to color the grid with some colors, satisfying the following condition:

  • If $(x_1,y_1)$, $(x_2,y_2)$ are two distinct cells with the same color, then $\max(|x_1-x_2|,|y_1-y_2|)\ge k$.

You don't like using too many colors. Please find the minimum number of colors needed to color the grid.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le1000$). The description of the test cases follows.

The only line of each test case consists of three positive integers $n$, $m$, $k$ ($1\le n,m,k\le10^4$) — the dimensions of the grid and the magic constant.

For each test case, print a single integer — the minimum number of colors needed to color the grid.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le1000$). The description of the test cases follows.

The only line of each test case consists of three positive integers $n$, $m$, $k$ ($1\le n,m,k\le10^4$) — the dimensions of the grid and the magic constant.

Output

For each test case, print a single integer — the minimum number of colors needed to color the grid.

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

Note

In the first test case, one of the optimal constructions is:

In the second test case, the color of all cells must be pairwise different, so the answer is $5$.