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

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

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

Входные данные

В первой строке дано количество тестов t (1 ≤ t ≤ 105). В следующих t строках даны тесты. Тест содержит одно целое число ni (1 ≤ ni < 10500001) - начальное значение n в i-м тесте. Суммарная длина чисел во всех тестах не превышает 500000.

Выходные данные

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