BC  Break the Chocolate
Benjamin is going to host a party for his big promotion coming up.
Every party needs candies, chocolates and beer, and of course Benjamin has prepared some of those. But as everyone likes to party, many more people showed up than he expected. The good news is that candies are enough. And for the beer, he only needs to buy some extra cups. The only problem is the chocolate.
As Benjamin is only a 'small court officer' with poor salary even after his promotion, he can not afford to buy extra chocolate. So he decides to break the chocolate cubes into smaller pieces so that everyone can have some.
He have two methods to break the chocolate. He can pick one piece of chocolate and break it into two pieces with bare hand, or put some pieces of chocolate together on the table and cut them with a knife at one time. You can assume that the knife is long enough to cut as many pieces of chocolate as he want.
The party is coming really soon and breaking the chocolate is not an easy job. He wants to know what is the minimum number of steps to break the chocolate into unitsize pieces (cubes of size 1×1×1). He is not sure whether he can find a knife or not, so he wants to know the answer for both situations.
Input
The first line contains an integer T (1 ≤ T ≤ 10000), indicating the number of test cases.
Each test case contains one line with three integers N, M, K (1 ≤ N, M, K ≤ 2000), meaning the chocolate is a cube of size N×M×K.
Output
For each test case in the input, print one line: "Case #X: A B", where X is the test case number (starting with 1) , A and B are the minimum numbers of steps to break the chocolate into N×M×K unitsize pieces with bare hands and knife respectively.
Example
Input: 2 1 1 3 2 2 2 Output: Case #1: 2 2 Case #2: 7 3
hide comments
exesharkx:
20190418 00:35:37
Requires Imagination 

karan_yadav:
20180705 07:29:06
SPOILER ALERT


returnofsk:
20180307 07:03:10
AC Last edit: 20180308 12:52:58 

sonuverma:
20180208 07:26:08
BC finaly AC :) 

piyushmittal:
20170216 13:29:31
nice problem .wrong understanding of question costed me two wrong answer


sai krishna:
20150812 17:22:45
200th Green Light :) 

[Mayank Pratap]:
20150523 06:46:26
Enjoyed this problem.. :) Gud one ... Bin Jin 

Abhinandan Agarwal:
20150228 00:19:43
good question ... thinking it wrong costed me 2 WAs ... its pretty difficult to nderstand d scenario with the knife , more test cases needed :P 

Gaurav sharma:
20140923 15:46:45
is there any special test case......???? 
Added by:  Bin Jin 
Date:  20111108 
Time limit:  0.352s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM/ICPC Regional Contest, Chengdu 2011 