Марта колекціонує банкноти й оцінює їх за серійними номерами. Серійний номер — це додатне ціле число, і Марта називає його красивим, якщо воно ділиться на суму своїх цифр у десятковому записі. Наприклад, красиве, бо сума його цифр рівна 1 + 1 + 0 = 2 і 110 = 2 \cdot 55; число не красиве, бо не ділиться на 1 + 3 = 4.
Найбільше Марта цінує красиві пари: дві банкноти, серійні номери яких — це два послідовні красиві цілі числа і x + 1. Наприклад, і утворюють красиву пару, адже ділиться на 1 + 1 + 1 = 3.
Марта збирається відвідати колекціонерів. У -го колекціонера є пачка, що містить рівно по одній банкноті з кожним серійним номером від m_i до 2m_i включно. Для кожного колекціонера вона хоче вибрати красиву пару в його пачці, тобто два послідовні красиві цілі числа і x + 1, для яких
або визначити, що такої пари немає.
Перший рядок містить одне ціле число (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
У першого колекціонера в пачці є банкноти і ; обидва числа красиві, тож вони утворюють єдину можливу красиву пару.
У другого колекціонера серійні номери — 8, 9, \ldots, 16. Серед них красивими є , , і , тож можливі рівно дві красиві пари: пари і .
У третього колекціонера серійні номери — 30, 31, \ldots, 60; жодні два послідовні числа з них не є одночасно красивими.
Для четвертого колекціонера одна з можливих відповідей — це 2754 = 18 \cdot 153 і 2755 = 19 \cdot 145, де і — їх суми цифр.
Для п'ятого колекціонера суми цифр чисел і дорівнюють і , і виконується, що 987654321987655230 = 90 \cdot 10973936910973947 та 987654321987655231 = 91 \cdot 10853344197666541.