Migrated from Lutece 370 K Service Stations

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a rectangular city with $N$ rows and $M$ columns, and every grid has some people living there. Now Alibaba wants to choose some grids to build $K$ service stations. The best way to build service stations is to make the largest distance among all distances between a grid and its nearest service station as short as possible. The distance between two grids $(x_1, y_1)$ and $(x_2, y_2)$ is $\max(|x_1-x_2|, |y_1-y_2|)$, where $|x|$ is the absolute value of $x$. Now it’s you work to build service stations optimally.

Input

The first line of input contains an integer $T$ ($T\leq 1000$), which is the number of data sets that follow.

Every test case consists of three integers $N$, $M$, $K$, which are specified before. $1\leq N, M, K\leq 1000000000$.

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and starts at $1$. Then output the largest distance among all distances between a grid and its nearest police station while you build police stations optimally.

Samples

3
1 1 1
2 2 1
3 3 1

Case #1: 0
Case #2: 1
Case #3: 1

Resources

The 9th UESTC Programming Contest Preliminary