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

• Запомнить младшую цифру числа n в десятичной записи.
• Пока n нацело не делится на 10, прибавлять запомненную цифру.
• Поделить n на 10, и вернуться к началу ритуала. Ритуал продолжается бесконечно, в книге написано, что наименьшее число, которому будет равно n в процессе этого ритуала — искомое число. Иван пока не определился с тем, какое изначальное n выбрать. Помогите ему для каждого начального варианта определить соответствующее число, которое принесет удачу в новом году.

Формат входных данных

В первой строке дано одно число t — количество тестов (1 ⩽ t ⩽ 100000).

В следующих t строках даны тесты. Тест содержит одно целое число n_i — начальное значение n в i-м тесте (1 ⩽ n_i < 10⁵⁰⁰⁰⁰¹).

Суммарная длина чисел во всех тестах не превышает 500000.

Формат выходных данных

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

Пример