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
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
Aquí:
S_{\mathrm{odd}}(A) es la suma de todos los dígitos a_i que son números impares;
S_{\mathrm{even}}(A) es la suma de todos los dígitos a_i que son números pares;
P_{\mathrm{odd}}(A) es la suma de todos los dígitos a_i que están en posiciones impares ;
P_{\mathrm{even}}(A) es la suma de todos los dígitos a_i que están en posiciones pares .
Por ejemplo, para A = 1234 tenemos a_0 = 4, a_1 = 3, a_2 = 2, a_3 = 1. Entonces:
S_{\mathrm{odd}} = 1 + 3 = 4;
S_{\mathrm{even}} = 2 + 4 = 6;
P_{\mathrm{odd}} = 3 + 1 = 4;
P_{\mathrm{even}} = 4 + 2 = 6.
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:
S_{\mathrm{odd}} = 4;
S_{\mathrm{even}} = 6;
P_{\mathrm{odd}} = 4 + 2 = 6;
P_{\mathrm{even}} = 0 + 3 + 1 = 4.
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.
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 .
Para cada consulta, imprime el número buscado en una línea separada, completo y sin ceros a la izquierda.
Ejemplo 1
Ejemplo 2
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.