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~ ó ~2110115~. En cambio, números como ~22, 10, 347~ ó ~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?

El Problema

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.

Entrada

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.

Salida

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.

Restricciones

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

• ~1 \leq N \leq 10^4~ Cantidad de números
• ~1 \leq X_i \leq 10^{100}~ Números a considerar

Nota sobre la Evaluación

Para un conjunto de casos que valen el 30% de los puntos, siempre se cumple ~N \leq 10~ y ~X_i \leq 10^5~. Para un conjunto de casos que valen el 60% de los puntos, siempre se cumple ~X_i \leq 10^9~.

Ejemplo de Entrada

5
123
20
52
5432
888

Ejemplo de Salida

123: 111
20: 25
52: 52
5432: 5522
888: 888