У самых истоков CrowdForces, ещё совсем давно, стояла именно Тётя Люсине. За это время она заработала много денег, даже забыла все цифры и теперь просто платит. Но совершенно неожиданно ей на ревью попалась задача как раз на цифры! Тётя Люсине не может решить даже on-ramp задачу. Помогите ей, ведь судьба вашего аккаунта в её руках!
Дано целое число \(n\) без нулей в десятичной записи. Алиса и Боб играют в игру с этим числом. Алиса начинает первой. Они делают ходы по очереди.
В своем ходу Алиса должна поменять местами любые две цифры в числе, стоящие на разных позициях. Боб в свой ход всегда удаляет последнюю цифру числа. Игра заканчивается, когда остаётся ровно одна цифра.
Вам необходимо найти минимальное число, которое Алиса может получить в результате игры.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное число, которое Алиса может получить в результате игры.
Примечание
В первом наборе входных данных Алиса должна поменять местами \(1\) и \(2\). После этого Боб удаляет последнюю цифру, т. е. \(1\), поэтому ответ \(2\).
Во втором наборе входных данных Алиса может поменять местами \(3\) и \(1\): \(312\). После этого Боб удаляет последнюю цифру: \(31\). Потом Алиса меняет местами \(3\) и \(1\): \(13\) и Боб удаляет \(3\), поэтому ответ \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
12
132
487456398
|
2
1
3
|