Mr. Narciso Armstrong is an exceptionally well educated gentleman. Everything he thinks and does adheres to the highest code of conduct. This includes all matters, even his wallet.

He recently discovered a very noble property of some numbers. If you take one of these numbers and sum all of it's digits to the power of the length of the number, then you get the same number back. Astonished by his discovery, he named these numbers after himself: narcissistic numbers.

For example: 54748 is such a number, as we see that 5⁵ + 4⁵ + 7⁵ + 4⁵ + 8⁵ = 3125 + 1024 + 16807 + 1024 + 32768 = 54748. Another such number is 371, as we can also see that 3³ + 7³ + 1³ = 27 + 343 + 1 = 371.

Being such a gentleman, Mr. Armstrong will never pay an amount of money that does not have this property. Therefore, if he wants to pay something with price P he will instead pay Q, where Q is the smallest number, greater or equal than P that is narcissistic.

Input

This first line of the input contains the number of tests cases T

T lines follow, each with a single non--negative integer P: the price of an item Mr. Armstrong wants to buy.

Output

For each case, print a single line containing the case number (see sample output for format) and the amount that Mr. Armstrong will pay.

Example

Input:
3
5
280
2543
Output:
Case #1: 5
Case #2: 370
Case #3: 8208

Constraints

• 1 ≤ T ≤ 10⁵

• All answers will fit a 32 bit signed integer