Контрольная цифра Луна

Алгоритм Луна приписывает к строке цифр одну контрольную так, чтобы получившаяся строка проходила проверку: идём справа налево, каждую вторую цифру удваиваем, а если удвоение дало больше девяти — вычитаем девять; сумма всех получившихся цифр должна делиться на 10.

По заданной строке выведите контрольную цифру, которую надо приписать справа.

В первой строке $q$ ($1 \le q \le 10^5$). В каждой из следующих $q$ строк — непустая строка из цифр длиной не больше 18.

Для каждой строки выведите контрольную цифру в отдельной строке.