Таинственный ритуал

Кратос нашел книгу, в которой описан таинственный ритуал. Изначально можно выбрать любое число $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$ в процессе ритуала.