VZLA2019G - Gentleman s Wallet

no tags 

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 55 + 45 + 75 + 45 + 85 = 3125 + 1024 + 16807 + 1024 + 32768 = 54748. Another such number is 371, as we can also see that 33 + 73 + 13 = 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 ≤ 105

• All answers will fit a 32 bit signed integer


hide comments
tarun_28: 2019-12-19 15:20:58

can you plz check my last submission? Am i missing something? any special test cases? getting WA:(

sriram_21: 2019-11-12 07:36:47

Read constraints properly youll get a hint

Rocker3011: 2019-11-07 20:30:12

I think the constrains need a little more definition , at least regarding the size of the integer P since solutions can vary a lot by knowing or not that constrain.

Last edit: 2019-11-07 20:30:31

Added by:Samuel Nacache
Date:2019-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Ricardo Monascal - Used for Venezuelan 2019 ICPC Local Contest