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