CF1684A.Digit Minimization

There is an integer $n$ without zeros in its decimal representation. Alice and Bob are playing a game with this integer. Alice starts first. They play the game in turns.

On her turn, Alice must swap any two digits of the integer that are on different positions. Bob on his turn always removes the last digit of the integer. The game ends when there is only one digit left.

You have to find the smallest integer Alice can get in the end, if she plays optimally.

有一个十进制表示中不含数字 $0$ 的整数 $n$。爱丽丝（Alice）和鲍勃（Bob）正在用这个整数进行一场游戏，爱丽丝先手，两人轮流进行操作。

在爱丽丝的回合中，她必须交换该整数中任意两个位于不同位置上的数字。而在鲍勃的回合中，他总是移除该整数的最后一位数字。当整数只剩下一位数字时，游戏结束。

你需要求出：若爱丽丝采取最优策略，最终所能得到的最小整数是多少？

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains the integer $n$ ($10 \le n \le 10^9$) — the integer for the game. $n$ does not have zeros in its decimal representation.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$10 \le n \le 10^9$），即游戏所用的整数。$n$ 的十进制表示中不含数字 $0$。

For each test case output a single integer — the smallest integer Alice can get in the end of the game.

对于每个测试用例，输出一个整数——即爱丽丝在游戏结束时能得到的最小整数。

In the first test case Alice has to swap $1$ and $2$. After that Bob removes the last digit, $1$, so the answer is $2$.

In the second test case Alice can swap $3$ and $1$: $312$. After that Bob deletes the last digit: $31$. Then Alice swaps $3$ and $1$: $13$ and Bob deletes $3$, so the answer is $1$.

在第一个测试用例中，Alice 必须交换 $1$ 和 $2$。之后 Bob 删除最后一位数字 $1$，因此答案为 $2$。

在第二个测试用例中，Alice 可以交换 $3$ 和 $1$：得到 $312$。之后 Bob 删除最后一位数字：得到 $31$。接着 Alice 交换 $3$ 和 $1$：得到 $13$，Bob 再删除 $3$，因此答案为 $1$。