| Reverse and Add |
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.
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.
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!
5 195 265 750 34543 196
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