Pares e impares#13071

Pares e impares

1,5 segundos
256 megabytes

Sea un número natural y sea a_{m-1} a_{m-2} \ldots a_1 a_0 su representación decimal sin ceros a la izquierda, es decir

A = a_0 + 10 \cdot a_1 + 10^2 \cdot a_2 + \ldots + 10^{m-1} \cdot a_{m-1}.

En otras palabras, los dígitos se numeran de derecha a izquierda, comenzando desde cero: a_0 es el último dígito (el dígito de las unidades), a_1 es el dígito de las decenas, y así sucesivamente. El número se llama posición del dígito a_i.

El número se llama equilibrado si

S_{\mathrm{odd}}(A) - P_{\mathrm{odd}}(A) = S_{\mathrm{even}}(A) - P_{\mathrm{even}}(A).

Aquí:

Por ejemplo, para A = 1234 tenemos a_0 = 4, a_1 = 3, a_2 = 2, a_3 = 1. Entonces:

Como se cumple que S_{\mathrm{odd}} - P_{\mathrm{odd}} = 4 - 4 = 0 y S_{\mathrm{even}} - P_{\mathrm{even}} = 6 - 6 = 0, el número es equilibrado.

Sin embargo, para A = 12340 las posiciones de todos los dígitos originales aumentan en uno: a_0 = 0, a_1 = 4, a_2 = 3, a_3 = 2, a_4 = 1. Ahora:

Como 4 - 6 \ne 6 - 4, el número no es equilibrado.

Se te dan consultas. En cada consulta se da un número natural . Encuentra el menor número equilibrado cuya representación decimal comience con la representación decimal del número . En otras palabras, se obtiene añadiendo k \ge 0 dígitos más a la derecha de (cualesquiera dígitos, incluidos ceros); se permite el caso k = 0, es decir, M = N. Se puede demostrar que tal número siempre existe.

Entrada

La primera línea contiene un único entero (1 \le Q \le 10^6) — la cantidad de consultas.

Cada una de las siguientes líneas contiene un único número natural , escrito sin ceros a la izquierda. Se garantiza que 1 \le |N| \le 10^6 y que la suma de sobre todas las consultas no supera 10^6, donde es la cantidad de dígitos del número .

Salida

Para cada consulta, imprime el número buscado en una línea separada, completo y sin ceros a la izquierda.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Nota

En el primer ejemplo:

  • ya es equilibrado por sí mismo (véase arriba), así que M = N.

  • no es equilibrado: S_{\mathrm{odd}} - P_{\mathrm{odd}} = 9 - 0 = 9, mientras que S_{\mathrm{even}} - P_{\mathrm{even}} = 0 - 9 = -9. Los siguientes candidatos son 90, 91, \ldots, 99; entre ellos, es equilibrado.

  • Para la respuesta es : aquí a_0 = 1, a_1 = 8, a_2 = 0, a_3 = 2, a_4 = 9, a_5 = 9, de modo que S_{\mathrm{odd}} - P_{\mathrm{odd}} = (1 + 9 + 9) - (8 + 2 + 9) = 0 y S_{\mathrm{even}} - P_{\mathrm{even}} = (8 + 0 + 2) - (1 + 0 + 9) = 0. Ningún número menor sirve.