有一个整数 $$$n$$$ 的十进制表示形式中没有零。 Alice 和 Bob 正在用这个整数玩一个游戏。爱丽丝先开始。他们轮流玩游戏。
轮到 Alice 时,她必须交换整数中不同位置的任意两位数字。轮到鲍勃时,他总是删除整数的最后一位数字。当只剩下一位数字时游戏结束。
如果 Alice 表现最佳,你必须找到 Alice 最终能得到的最小整数。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含整数 $$$n$$$ ($$$10 \le n \le 10^9$$$) — 游戏的整数。 $$$n$$$ 的十进制表示形式中没有零。
输出
对于每个测试用例,输出一个整数——Alice 在游戏结束时可以获得的最小整数。
示例
输入 #1
3 12 132 487456398
输出 #1
2 1 3
注意
在第一个测试用例中,Alice 必须交换 $$$1$$$ 和 $$$2$$$。之后鲍勃删除最后一位数字$$$1$$$,所以答案是$$$2$$$。
在第二个测试用例中,Alice 可以交换 $$$3$$$ 和 $$$1$$$:$$$312$$$。之后鲍勃删除了最后一个数字:$$$31$$$。然后 Alice 交换 $$$3$$$ 和 $$$1$$$:$$$13$$$,Bob 删除 $$$3$$$,所以答案是 $$$1$$$。