Tuenti Challenge 10

Challenge 13 - The Great Toilet Paper Fortress

You work at a supermarket. And, due to some unexpected circumstances, people think that you're running out of toilet paper. Thankfully, however, your stock is pretty large. The manager has now asked you to build the biggest possible fortress using toilet paper packs. You won’t be opening the packs, you'll just build the fortress using the packs that customers will buy later. This way, buyers can be sure that there won't be a toilet paper shortage any time soon.

The fortress will have a central tower, which will be the tallest point of the fortress. And there must be at least one layer of walls surrounding the tower. You have the following instructions for building it:

  • Step 1: Start with the central tower. It must be at least three packs tall. From the top, it will be seen as either a square or a rectangle. If it's a rectangle, the difference between the two dimensions can only be one pack.
  • Step 2: Surround the previous packs, by making a new rectangular layer. This layer must have a height of two packs less than the previous one.
  • Step 3: Surround again, this time with a rectangular layer that is one pack taller than the previous one (one pack shorter than the layer that the previous step surrounded).
  • Step 4: If the last layer was two packs tall (which means that step 3’s layer was only one pack tall), you have finished. Otherwise, repeat steps 2 to 4.

Given a number of toilet paper packs, you must choose the highest possible fortress height. After that, you must choose the central tower dimensions that will make you use as many toilet paper packs as you can.

Input

The first line contains the number of cases C. Then, C lines follow, each with the number of toilet paper packs P for that case.

Output

For each case, output 'Case #X: H M', where X is the case number (the first case has number 1), H is the maximum height of the tower, and M is the maximum amount of packs you can use for building a fortress with that height. If it's not possible to build any fortress with the specified number of packs, write 'Case #X: IMPOSSIBLE' instead.

Limits

  • 1 ≤ C ≤ 100
  • 1 ≤ P ≤ 262

Sample Input

3
20
76
160

Sample Output

Case #1: IMPOSSIBLE
Case #2: 3 76
Case #3: 4 156

In the first case, it's impossible to build a fortress of height 3.
In the second case, we build a fortress with a central tower of height 3 and 3x2 size.
In the third case, we build a fortress with a central tower of height 4 and 1x1 size.

Diagram of the second case:

2 2 2 2 2 2 2
2 1 1 1 1 1 2
2 1 3 3 3 1 2
2 1 3 3 3 1 2
2 1 1 1 1 1 2
2 2 2 2 2 2 2

Diagram of the third case:

2 2 2 2 2 2 2 2 2
2 1 1 1 1 1 1 1 2
2 1 3 3 3 3 3 1 2
2 1 3 2 2 2 3 1 2
2 1 3 2 4 2 3 1 2
2 1 3 2 2 2 3 1 2
2 1 3 3 3 3 3 1 2
2 1 1 1 1 1 1 1 2
2 2 2 2 2 2 2 2 2

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want. Be careful with extra whitespace. The output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you have to solve the test phase before you can submit your code. You must provide the source code used to solve the challenge and you can only make one submission. After your solution is submitted, you won't be able to modify it to fix issues or make it faster.

If you have any doubts, please see the info section.