Programacion Competitiva Bolivia

Muchos dispositivos, tales como una calculadora o un reloj digital, muestran los números usando el sistema SSD (seven-segment display). El funcionamiento de este sistema es muy sencillo, y consta de siete pequeños segmentos que pueden estar encendidos o apagados dependiendo del número que se quiera representar, tal como se aprecia en la figura siguiente:

Un día Rafael estaba frente al espejo con su calculadora, cuando se dio cuenta de que el número que aparecía en la pantalla, que era 2005, se veía exactamente igual en el reflejo del espejo.

A Rafael le pareció interesante, e intentó descubrir qué otros números cumplen también esta propiedad. Para ello, empezó por escribir en la calculadora todos los dígitos posibles, fijándose en su reflejo en el espejo, como se indica en la figura siguiente:

Los dígitos '0', '1' y '8' se ven "iguales" cuando se reflejan en el espejo, es decir, representan el mismo dígito. El dígito '2' se transforma en un '5' (y viceversa). En cambio los dígitos '3', '4', '6', '7'y '9' no representan ningún otro dígito válido cuando se reflejan en el espejo. Hay que tener en cuenta que, además de estas transformaciones en cada dígito, el número aparece invertido. Es decir, en el reflejo, el dígito de más a la izquierda pasa a ser el dígito de más a la derecha, y así sucesivamente.

Cuando el reflejo de un número en el espejo representa exactamente el número original sin reflejar, decimos que el número presenta "simetría de reflexión". Los primeros 10 números enteros positivos con esta propiedad son los siguientes: 1, 8, 11, 25, 52, 88, 101, 111, 181 y 205. Números más grandes también con esta propiedad son por ejemplo 8528 o 2110115. En cambio, números como 22, 10, 347 o 6776 no presentan esta característica.

Dado un número cualquiera, Rafael pensó que sería interesante descubrir cual es el número más cercano que presenta simetría de reflexión. Por ejemplo, dado el 200, la respuesta sería 205, ya que ningún otro número con la propiedad deseada está más cerca del 200. Por ejemplo, 181 también tiene la simetría que queremos, pero está más lejos, ya que |200-181| es mayor que |205-200|. ¿Podrías ayudar a Rafael a llevar a cabo esta tarea?

Dada una lista de N números enteros positivos, hay que descubrir cual es el número con simetría de reflexión más cercano a cada uno de ellos. Si el número dado ya presenta esta simetría, la respuesta es el propio número original. En caso contrario, hay que calcular el número entero con simetría de reflexión con menor diferencia en valor absoluto respecto al número dado. Si existiera más de un número con la misma diferencia, hay que escribir el menor.

Input

La primera línea contiene la cantidad de números a considerar N.

A continuación vienen exactamente N líneas. Cada una de ellas contiene un único entero positivo X_i, que indica el i-ésimo número dado. Estos números pueden aparecer en cualquier orden y puede haber números repetidos.

Se garantiza que todos los casos de prueba cumplen los límites siguientes:

Output

Hay que escribir N líneas, cada una de ellas siguiendo el formato "X_i: Y_i" (sin las comillas), donde Y_i es el número con simetría de reflexión más cercano a X_i (el menor en caso de empate), tal como se describió anteriormente. Lógicamente, los números se deben mostrar en el mismo orden en el que aparecen en la entrada.

Example

Input:
5
123
20
52
5432
888
Output:
123: 111
20: 25
52: 52
5432: 5522
888: 888