Таємничий ритуал
Кратос знайшов книгу, в якій описано таємничий ритуал. Спочатку можна вибрати будь-яке число n. З ним слід виконувати наступні дії:
Запам'ятати молодшу цифру числа n у десятковому записі.
Поки n не ділиться націло на 10, додавати запам'ятану цифру.
Поділити n на 10 і повернутися до початку ритуалу.
Ритуал триває безкінечно, у книзі написано, що найменше число, якому буде дорівнювати n у процесі цього ритуалу - магічне. Кратос поки не визначився з тим, яке початкове n вибрати. Допоможіть йому для кожного початкового варіанта визначити відповідне магічне число.
Вхідні дані
У першому рядку задано кількість тестів t (1 ≤ t ≤ 10^5). У наступних t рядках дано тести. Тест містить одне ціле число n[i] (1 ≤ n[i] < 10^500001) - початкове значення n в i-му тесті. Сумарна довжина чисел у всіх тестах не перевищує 500000.
Вихідні дані
Для кожного тесту виведіть у новому рядку одне число - мінімальне значення, якому коли-небудь буде дорівнювати n у процесі ритуалу.