A. Много цифр
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У самых истоков CrowdForces, ещё совсем давно, стояла именно Тётя Люсине. За это время она заработала много денег, даже забыла все цифры и теперь просто платит. Но совершенно неожиданно ей на ревью попалась задача как раз на цифры! Тётя Люсине не может решить даже on-ramp задачу. Помогите ей, ведь судьба вашего аккаунта в её руках!

Дано целое число $$$n$$$ без нулей в десятичной записи. Алиса и Боб играют в игру с этим числом. Алиса начинает первой. Они делают ходы по очереди.

В своем ходу Алиса должна поменять местами любые две цифры в числе, стоящие на разных позициях. Боб в свой ход всегда удаляет последнюю цифру числа. Игра заканчивается, когда остаётся ровно одна цифра.

Вам необходимо найти минимальное число, которое Алиса может получить в результате игры.

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

В первой строке входных данных находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В единственной строке описания каждого набора входных данных находится одно целое число $$$n$$$ ($$$10 \le n \le 10^9$$$) — число, с которым ведётся игра. $$$n$$$ не содержит нулей в десятичной записи.

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

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

Пример
Входные данные
3
12
132
487456398
Выходные данные
2
1
3
Примечание

В первом наборе входных данных Алиса должна поменять местами $$$1$$$ и $$$2$$$. После этого Боб удаляет последнюю цифру, т. е. $$$1$$$, поэтому ответ $$$2$$$.

Во втором наборе входных данных Алиса может поменять местами $$$3$$$ и $$$1$$$: $$$312$$$. После этого Боб удаляет последнюю цифру: $$$31$$$. Потом Алиса меняет местами $$$3$$$ и $$$1$$$: $$$13$$$ и Боб удаляет $$$3$$$, поэтому ответ $$$1$$$.