It is the year 4016 and BUET is organizing yet another inter university programming contest. Contestants from all around the galaxy are gathering to attend this grand galactic event. The final count of the contestants tallied to an impressive value of 1018.
The coordinator of the contest, Sir Kaizer Von Abaddon, distributed each of the 1018 contestants with their own unique identification number (ID) ranging from 1 to 1018. But something really bothered Sir Kaizer, he has always hated perfect powers, which are integers that can be expressed as an positive integer power of another number. If a number has greater exponent he will dislike it more and he only considers the representation for which the value of the exponent is the greatest (for example: 64 can be represented as 641, 82, 43 and 26, but he will only consider the last one since that has the greatest exponent value). Therefore he decided to be a bit unfair to those whose IDs are a perfect power.
On the day of the contest once all the 1018 participants arrived at the campus, they were asked to form a single line to get their belongings checked. At first the contestants stood at some random order but Sir Kaizer soon asked everyone to exchange their positions till the entire line was sorted according to the value of their ID’s exponent representation, that is if two IDs are represented as ap and bq, ap would move somewhere front of bq given p is smaller than q. Furthermore only if p and q are equal, ap would move to the front of bq if a is smaller than b. Even though the contestant had no idea why they had to do it, they did it till there were no more position exchange possible. This way Sir Kaizer ensured that the ones with ID he hated were behind in the line and had to wait more before their turn came and thus they suffered more, maybe they might even withdraw from the contest from getting tired for waiting so long! No one did though, even though they were a bit irritated.
For example: the participant with ID 100000 now has earlier position in the line to the participant with ID 64, since 100000 can be represented as 105, while 64 is represented as 26 and the former has lower exponent value. The sequence of IDs of the contestants in the line would now look something like this:
2, 3, 5, 6, … 4, 9, 25, … 100000, … 64, … 576460752303423488, 1
Now Sir Kaizer wonders which contestant appears at some particular position within the line. He asks you some positions and you have to tell him the ID of the participants who appear in those positions.
First line of the input is T (1 ≤ T ≤ 5000) which describes the number of positions questioned by Sir Kaizer, followed by T lines. Each line contains an integer P (1 ≤ P ≤ 1018) denoting the position in that line. Remember that the total number of contestant is always 1018.
For each question print a line with the format: “Case N: X”, where N is question number and X is the ID of the contestant appearing on the position asked on the Nth question.
| Input | Output |
|---|---|
4 1 3 1000000000000000000 999999999999999999 | Case 1: 2 Case 2: 5 Case 3: 1 Case 4: 576460752303423488 |