URI Online Judge | 1785

Kaprekar

By Duhan Caraciolo, UFPE BR Brazil

Timelimit: 1

The number 6174 is known as Krapekar’s constant after the Indian mathematician Dattathreya Ramachandra Kaprekar. This number is interesting because of the following fact: let X be any 4-digit number (leading 0’s are allowed) in which not all of them are the same, then Krapekar’s routine starting at this number always converge to 6174. That is, Krapekar’s routine converges to 6174 if, and only if, X is a 4-digit number and at least two of them are pairwise different. Krapekar’s routine is defined as follows:


int krapekar(int X) {

   int cnt = 0;

   while (X != 6174) {

       int hi = highest_number_with_digits_of(X);

       int lo = lowest_number_with_digits_of(X);

       X = hi - lo;

       cnt = cnt + 1;

   }

   return cnt;

}


highest_number_with_digits_of(X) is the highest number that can be made using X’s digits.

lowest_number_with_digits_of(X) is the lowest number that can be made using X’s digits.


For example:

highest_number_with_digits_of(3524) = 5432

lowest_number_with_digits_of(3524) = 2345

highest_number_with_digits_of(10) = 1000 //because 10 = 0010 with four digits.

lowest_number_with_digits_of(10) = 1

Input

The first line contains an integer T (1 ≤ T ≤ 10⁴), the number of test cases. Each test case consists of a line containing an integer X (0 ≤ X ≤ 9999).

Output

For each test case print “Caso #X: Y”, where X is the number of the current case, starting at 1, and Y is the return of Krapekar’s routine or -1 in case it stays in an infinite loop.

Input Sample Output Sample

3
3524
0
10

Caso #1: 3
Caso #2: -1
Caso #3: 5