Success Party

0

0 votes
Problem

All the events of NU-Tech'15 have completed successfully and the whole NU-Tech team is celebrating. Drinks are being served to one and all. But there arises a new problem, shortage of Ice Cubes for the drinks. There is only a large Ice Cube available which has to be broken into cubes of Unit Dimensions (1 x 1 x 1). Now, there are two ways of breaking the Ice. You can pick a Large piece and break it into two pieces with bare hand, or put some pieces of Ice Cubes together on the table and cut them with a knife at one time. You can assume that the knife is long enough and sharp enough to cut as many pieces of Ice Cubes as we want.

enter image description here

Input:

The first line contains an integer t, indicating the number of test cases.

Each test case contains one line with three integers N, M, K, meaning the Ice Cube is 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 Ice Cube into N×M×K unit-size pieces with bare hands and knife respectively.

Constraints:

1 ≤ t ≤ 10000

1 ≤ N, M, K ≤ 2000

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?