Problem C
King’s Wish
Input: Standard
Input
Output: Standard
Output
Once there was a king in a country far far away. He had his own sense of beauty and some knowledge in mathematics. He built a large hall room for his meetings which is square shaped and had a length of K. The king wanted to cover the floor of the hall with tiles. But he was interested to make his room special, so he imposed the following conditions on tile size:
- Tiles must be of rectangular (square shape is not allowed) shape of length L and width W. Both must be integer and L must be strictly greater than W (L > W). (What is the point of filling square shape room with square shape tile?)
- The length of the tile L must be strictly less than K (L < K). (The beauty of tiling loses if one tile covers the entire length).
- The room must be covered with integer number of complete tiles. Tiles are not allowed to be broken. Also, tiles must not overlap. However, tiles can be put both horizontally and vertically.
- One should not be able to fill a square whose side is less than K using the tile of (L, W) size. For example, if K = 6, you cannot use (2, 1) tile as you can fill 4x4 square with it. (The king does not like smaller replica of his room with same size of tile).
- The king likes stripe shape, so among all possibilities that comply all the above conditions, the king would like to have the one which has the largest difference between length and width, in other words, for which (L – W) is maximized. If there is still a tie, the king would choose the one that that has larger perimeter.
The designer was in a fix looking at all these conditions. However he was also good enough with mathematics and after some days he could come up with a solution to make the king happy.
In this problem you have to do the same task. Given the value of K you must determine length L and width W of the desired tile.
Input
The first line of input will be an integer T (T < 1000) denoting the number of test cases. Each of the following lines will contain a positive integer K (K < 1012) denoting the length of the square.
Output
For each K produce one line of output starting with the case number in the format “Case d: “, where d is input number starting from 1. Then output two integers L and W which denote the length and width of the tile respectively separated by a space. If it is impossible to find tile sizes that fulfills all the conditions above, print the string “Impossible” instead. See sample input output for more detail.
Sample
Input Output
for Sample Input
|
3 |
Case
1: 9 2 |
Problemsetter: Towhidul Islam Talukder
Special Thanks to: Jane Alam Jan