LOSTBOX - Width of The Lost Box

Minas had a box of marble which is lost last week. About that box Minas only know that length and height of the box was L and H, and box contains K marbles. But he forget the width of the box. But he remember that width = 2 * radius of marble and width is also an integer. You can assume that all marble are same.

Now, Minas will give you L, H and K. You need to tell him the width of the box. If the width is less than 1 then print -1.

Input

Input starts with an integer T (1<=T<=1000), denoting the number of test cases.
Each case contains 3 integer L (1 ≤ L ≤ 10^9), H (1 ≤ H ≤ 10^9) and K (1 ≤ K ≤ 10^9).

Output

For each case of input, print the case number as "Case #: x", # is replaced by the case number starting from 1 and x is replaced by the maximum possible width of the box.

Example

Input:
1
2 2 4

Output:
Case 1: 1

Added by:imranziad
Date:2016-11-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:AIUB CS Fest 2016

hide comments
2019-07-08 05:18:31
Thanks Hodobox; I didn't even think, looking at the statement before, that the marbles are arranged in a rectangular grid.

An important lesson derived from solving this: 10//3 * 11//2 = 16.
2019-01-01 04:24:12
Clarifying since I found it unclear: you are to find the largest possible integer width W, so that at least K marbles with diameter W will fit stacked right on top of each other in a L*H*W box. If W = 0, then print -1 instead.

4
10 5 50
10 5 51
10 5 1
10 5 10
Your Output
Case 1: 1
Case 2: -1
Case 3: 5
Case 4: 2

In the fourth case, by having width 2, you can fit 2 rows of 5 marbles (of diameter 2). If the width was 3 (and so the diameter of the marbles as well), you could only fit 1 row of 3 marbles.
2017-01-14 08:54:11
If we assume the box completey filled with marbles, the my formula is absolutely correct, don't know why I'm getting WA :(
2016-12-15 15:30:55
more test cases plz ...!!!!
2016-12-08 13:08:42
Isn`t is like that, there should be an extra Parameter i.e. Width(thickness) of marble ..

Last edit: 2016-12-08 13:15:08
2016-11-27 22:37:10
Do we have to consider the voids as well created because of marbles ??
2016-11-27 10:30:06 Vipul Srivastava
Very good question.

Last edit: 2016-11-27 17:52:12
2016-11-27 08:28:05
This problem is very easy. I tried it with different IDEs online and am getting the right answer but here it says that my answer is wrong :/ Please help
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.