Reverse and Add

The Problem

The "reverse and add" method is simple: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure.

For example:

 195 Initial number
 591
-----
 786
 687
-----
1473
3741
-----
5214
4125
-----
9339 Resulting palindrome

In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.

Task

If a resulting palindrome exists in 1000 iterations (additions) or less, your program must compute the resulting palindrome and the number of iterations.

If a resulting palindrome does not exist within 1000 iterations (additions), your program must compute the number of decimal digits in the 1000th number that is obtained through the additions. For example, if the 1000th number is 123456789012345, the number of decimal digits is 15.

Input File: reverse.in

The first line will be an integer N (N ≥ 0), the number of test cases. The next N lines will each contain an integer P (P ≥ 0) for which your program must attempt to compute its palindrome. You may assume that all inputs will fit into Java's int type.

Output File:reverse.out

When a palindrome P is found after A additions, print P found after A additions on a separate line.

When no palindrome is found after 1000 additions and the length of the current candidate is L, print Probably no solution, candidate length is L on a separate line. Note: the current candidate might be much bigger than Java's int type!

Sample Input

5
195
265
750
34543
196

Sample Output

9339 found after 4 additions
45254 found after 5 additions
6666 found after 3 additions
34543 found after 0 additions
Probably no solution, candidate length is 411