Таємничий ритуал#11031

Умова Обговорення

Таємничий ритуал

1 секунда

128 мегабайтів

Середня

Кратос знайшов книгу, в якій описано таємничий ритуал. Спочатку можна вибрати будь-яке число $n$ . З ним слід виконувати наступні дії:

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

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

Вхідні дані

У першому рядку задано кількість тестів $t$ (1 \le t \le 10^5). У наступних $t$ рядках дано тести. Тест містить одне ціле число n_i (1 \le n_i < 10^{500001}) - початкове значення $n$ в $i$ -му тесті. Сумарна довжина чисел у всіх тестах не перевищує $500000$ .

Вихідні дані

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

Приклади

Приклад 1

Loading

Loading

1 \leq t \leq 1 0^{5}

n_{i}

1 \leq n_{i} < 1 0^{500001}