Pares coleccionables#13069

Pares coleccionables

0,5 segundos
256 megabytes

Marta colecciona billetes y los evalúa por sus números de serie. Un número de serie es un entero positivo, y Marta lo llama hermoso si es divisible por la suma de sus dígitos en notación decimal. Por ejemplo, es hermoso, porque la suma de sus dígitos es igual a 1 + 1 + 0 = 2 y 110 = 2 \cdot 55; el número no es hermoso, porque no es divisible por 1 + 3 = 4.

Lo que Marta más valora son los pares hermosos: dos billetes cuyos números de serie son dos enteros hermosos consecutivos y x + 1. Por ejemplo, y forman un par hermoso, ya que es divisible por 1 + 1 + 1 = 3.

Marta va a visitar a coleccionistas. El -ésimo coleccionista tiene un fajo que contiene exactamente un billete por cada número de serie desde m_i hasta 2m_i inclusive. Para cada coleccionista, ella quiere elegir un par hermoso en su fajo, es decir, dos enteros hermosos consecutivos y x + 1 para los cuales

m_i \le x \quad \text{y} \quad x + 1 \le 2m_i,

o determinar que tal par no existe.

Entrada

La primera línea contiene un único entero (1 \le q \le 10^5) — la cantidad de coleccionistas.

Cada una de las siguientes líneas contiene un único entero m_i (m_i \ge 1), escrito en notación decimal sin ceros a la izquierda. La cantidad total de dígitos de todos los m_i no supera 10^6 (\sum |m_i| \le 10^6).

Salida

Imprima líneas, la -ésima de las cuales es la respuesta para el -ésimo coleccionista.

Si en el fajo del -ésimo coleccionista hay un par hermoso (x, x+1), imprima el número en notación decimal sin ceros a la izquierda. Si hay varias respuestas posibles, imprima cualquiera de ellas.

Si en el fajo no hay ningún par hermoso, imprima un único número .

Ejemplos

Ejemplo 1

Loading
Loading

Nota

El primer coleccionista tiene en su fajo los billetes y ; ambos números son hermosos, así que forman el único par hermoso posible.

Los números de serie del segundo coleccionista son 8, 9, \ldots, 16. Entre ellos, los hermosos son , , y , así que hay exactamente dos pares hermosos posibles: los pares y .

Los números de serie del tercer coleccionista son 30, 31, \ldots, 60; entre ellos no hay dos números consecutivos que sean ambos hermosos.

Para el cuarto coleccionista, una de las respuestas posibles es 2754 = 18 \cdot 153 y 2755 = 19 \cdot 145, donde y son sus sumas de dígitos.

Para el quinto coleccionista, las sumas de dígitos de y son iguales a y , y se cumple que 987654321987655230 = 90 \cdot 10973936910973947 y 987654321987655231 = 91 \cdot 10853344197666541.