Колекційні пари#13069

Колекційні пари

0,5 секунди
256 мегабайтів

Марта колекціонує банкноти й оцінює їх за серійними номерами. Серійний номер — це додатне ціле число, і Марта називає його красивим, якщо воно ділиться на суму своїх цифр у десятковому записі. Наприклад, красиве, бо сума його цифр рівна 1 + 1 + 0 = 2 і 110 = 2 \cdot 55; число не красиве, бо не ділиться на 1 + 3 = 4.

Найбільше Марта цінує красиві пари: дві банкноти, серійні номери яких — це два послідовні красиві цілі числа і x + 1. Наприклад, і утворюють красиву пару, адже ділиться на 1 + 1 + 1 = 3.

Марта збирається відвідати колекціонерів. У -го колекціонера є пачка, що містить рівно по одній банкноті з кожним серійним номером від m_i до 2m_i включно. Для кожного колекціонера вона хоче вибрати красиву пару в його пачці, тобто два послідовні красиві цілі числа і x + 1, для яких

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

або визначити, що такої пари немає.

Вхідні дані

Перший рядок містить одне ціле число (1 \le q \le 10^5) — кількість колекціонерів.

Кожен із наступних рядків містить одне ціле число m_i (m_i \ge 1), записане в десятковій системі без провідних нулів. Сумарна кількість цифр у всіх m_i не перевищує 10^6 (\sum |m_i| \le 10^6).

Вихідні дані

Виведіть рядків, -й з яких є відповіддю для -го колекціонера.

Якщо в пачці -го колекціонера є красива пара (x, x+1), виведіть число у десятковому записі без провідних нулів. Якщо можливих відповідей декілька, виведіть будь-яку з них.

Якщо в пачці немає красивої пари, виведіть одне число .

Приклади

Приклад 1

Loading
Loading

Примітка

У першого колекціонера в пачці є банкноти і ; обидва числа красиві, тож вони утворюють єдину можливу красиву пару.

У другого колекціонера серійні номери — 8, 9, \ldots, 16. Серед них красивими є , , і , тож можливі рівно дві красиві пари: пари і .

У третього колекціонера серійні номери — 30, 31, \ldots, 60; жодні два послідовні числа з них не є одночасно красивими.

Для четвертого колекціонера одна з можливих відповідей — це 2754 = 18 \cdot 153 і 2755 = 19 \cdot 145, де і — їх суми цифр.

Для п'ятого колекціонера суми цифр чисел і дорівнюють і , і виконується, що 987654321987655230 = 90 \cdot 10973936910973947 та 987654321987655231 = 91 \cdot 10853344197666541.