28804번 - Таинственный ритуал 다국어

Кратос нашел книгу, в которой описан таинственный ритуал. Изначально можно выбрать любое число $n$. С ним следует производить следующие действия:

• Запомнить младшую цифру числа $n$ в десятичной записи.
• Пока $n$ нацело не делится на $10$, прибавлять запомненную цифру.
• Поделить $n$ на $10$, и вернуться к началу ритуала.

Ритуал продолжается бесконечно, в книге написано, что наименьшее число, которому будет равно $n$ в процессе этого ритуала --- магическое. Кратос пока не определился с тем, какое изначальное $n$ выбрать. Помогите ему для каждого начального варианта определить соответствующее магическое число.

В первой строке дано одно число $t$ --- количество тестов ($1 \le t \le 100\,000$).

В следующих $t$ строках даны тесты. Тест содержит одно целое число $n_i$ --- начальное значение $n$ в $i$-м тесте ($1 \le n_i < 10^{500\,001}$).

Суммарная длина чисел во всех тестах не превышает $500\,000$.

Для каждого теста выведите на новой строке одно число --- минимальное значение, которому когда-либо будет равно $n$ в процессе ритуала.