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 (x1, y1) and (x2, y2) is max(|x1-x2|, |y1-y2|), 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 <= 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 <= N, M, K <= 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.
 

Sample Input
3
1 1 1
2 2 1
3 3 1

 

Sample Output
Case #1: 0
Case #2: 1
Case #3: 1

chinese,please!