Problema número 205

Números de Lychrel

Tiempo máximo: 4,000 sMemoria máxima: 4096 KiB

Cuando se aburren, los aficionados a las matemáticas se dedican a jugar con los números. Eso les lleva, por ejemplo, a coger cualquier número, darle la vuelta y sumarlo a sí mismo, repitiendo el proceso una y otra vez hasta dar con un número capicúa. Por ejemplo, para el 91 llegamos a un capicúa en sólo dos pasos:

91 + 19 = 110
110 + 011 = 121

Algunos números se resisten a alcanzar un capicúa. El 196 es el número más pequeño para el que no se ha llegado a ninguno, por más que se ha intentado. Los matemáticos no han podido demostrar que, efectivamente, no vaya a llegarse a uno. Mientras continúan buscando una demostración, los aficionados siguen sumando y sumando con la esperanza de llegar a él. Los números con los que, se sospecha, no puede alcanzarse un capicúa se conocen como números de Lychrel. Curiosamente, algunos números capicúa parecen ser también números de Lychrel.

Entrada

La entrada comienza con un número indicando la cantidad de casos de prueba que vendrán a continuación. Cada caso de prueba estará compuesto de un número 1 ≤ n ≤ 100.000.

Salida

Para cada caso de prueba n, el programa deberá indicar el número de iteraciones que hay que dar hasta llegar a un número capicúa, seguido del número capicúa alcanzado. Si durante el proceso se llega a un número mayor que 1.000.000.000, se deberá asumir que el capicúa no es alcanzable y escribir "Lychrel?"*.

Entrada de ejemplo

4
91
196
4994
5445

Salida de ejemplo

2 121
Lychrel?
Lychrel?
4 79497
1Esta suposición es falsa y se usa para simplificar el problema. A modo de ejemplo, el número 10.677 alcanza el capicúa 4.668.731.596.684.224.866.951.378.664, de 28 dígitos, tras 53 iteraciones. Sin embargo, el programa escribirá, para ese número, "Lychrel?".