Problema E - La secuencia de Maribel

Entrada: secuencia.in
Salida: estándar
Tiempo límite: 3 segundos

Descripción

Maribel ha descubierto una secuencia que es decreciente N1 > N2 > … > Nm que se puede obtener a partir de cualquier número entero N > 9. Definido de la siguiente forma:

• N1 = N
• Nk+1 = Producto de los dígitos del número Nk en base 10 distintos de cero, (k > 0). Si Nk+1 es menor que 10, la secuencia termina.

Por ejemplo la secuencia de Maribel que se obtiene a partir del número 546546 es:

546546, 14400, 16, 6.

Has un programa que encuentre el último número de la secuencia de Maribel que se obtiene a partir de un número N.

Entrada

En la primera línea de entrada habrá un entero c (0 < c ≤ 100) que representa en número de casos a procesar. Cada caso de entrada consiste de una sola línea que contiene un número N (9 < N < 10^1000).

Salida

Por cada caso de entrada debes imprimir el último valor de la secuencia de Maribel que se obtiene a partir de N.

Ejemplo de entrada	Ejemplo de salida
3 3333 546546 10404	8 6 6

Regresar