Нехай — натуральне число, а a_{m-1} a_{m-2} \ldots a_1 a_0 — його десятковий запис без провідних нулів, тобто
Іншими словами, цифри нумеруються справа наліво, починаючи з нуля: a_0 — остання цифра (цифра одиниць), a_1 — цифра десятків і так далі. Число називається позицією цифри a_i.
Число називається збалансованим, якщо
Тут:
S_{\mathrm{odd}}(A) — сума всіх цифр a_i, які є непарними числами;
S_{\mathrm{even}}(A) — сума всіх цифр a_i, які є парними числами;
P_{\mathrm{odd}}(A) — сума всіх цифр a_i, що стоять на непарних позиціях ;
P_{\mathrm{even}}(A) — сума всіх цифр a_i, що стоять на парних позиціях .
Наприклад, для A = 1234 маємо a_0 = 4, a_1 = 3, a_2 = 2, a_3 = 1. Тоді:
S_{\mathrm{odd}} = 1 + 3 = 4;
S_{\mathrm{even}} = 2 + 4 = 6;
P_{\mathrm{odd}} = 3 + 1 = 4;
P_{\mathrm{even}} = 4 + 2 = 6.
Оскільки виконується S_{\mathrm{odd}} - P_{\mathrm{odd}} = 4 - 4 = 0 і S_{\mathrm{even}} - P_{\mathrm{even}} = 6 - 6 = 0, число збалансоване.
Проте для A = 12340 позиції всіх початкових цифр збільшуються на одиницю: a_0 = 0, a_1 = 4, a_2 = 3, a_3 = 2, a_4 = 1. Тепер:
S_{\mathrm{odd}} = 4;
S_{\mathrm{even}} = 6;
P_{\mathrm{odd}} = 4 + 2 = 6;
P_{\mathrm{even}} = 0 + 3 + 1 = 4.
Оскільки 4 - 6 \ne 6 - 4, число не є збалансованим.
Задано запитів. У кожному запиті дано натуральне число . Знайдіть найменше збалансоване число , десятковий запис якого починається з десяткового запису числа . Іншими словами, отримується дописуванням праворуч від ще k \ge 0 цифр (будь-яких, зокрема нулів); випадок k = 0, тобто M = N, дозволений. Можна довести, що таке число завжди існує.
Перший рядок містить одне ціле число (1 \le Q \le 10^6) — кількість запитів.
Кожен з наступних рядків містить одне натуральне число , записане без провідних нулів. Гарантується, що 1 \le |N| \le 10^6 та сума за всіма запитами не перевищує 10^6, де — це кількість цифр числа .
Для кожного запиту виведіть шукане число в окремому рядку повністю, без провідних нулів.
Приклад 1
Приклад 2
У першому прикладі:
саме є збалансованим (див. вище), тож M = N.
не є збалансованим: S_{\mathrm{odd}} - P_{\mathrm{odd}} = 9 - 0 = 9, тоді як S_{\mathrm{even}} - P_{\mathrm{even}} = 0 - 9 = -9. Наступні кандидати — це 90, 91, \ldots, 99; серед них збалансоване.
Для відповідь дорівнює : тут a_0 = 1, a_1 = 8, a_2 = 0, a_3 = 2, a_4 = 9, a_5 = 9, тож S_{\mathrm{odd}} - P_{\mathrm{odd}} = (1 + 9 + 9) - (8 + 2 + 9) = 0 і S_{\mathrm{even}} - P_{\mathrm{even}} = (8 + 0 + 2) - (1 + 0 + 9) = 0. Жодне менше число не підходить.