题目描述

有一个用十进制表示的没有前导零的正整数 $n$ 。Alice 和 Bob 正在用这个数玩一个游戏。Alice 先手，他们轮流进行游戏。

在她的这一轮中，Alice 应该交换这个数中的任何不同位置的两位。轮到 Bob 时，他每次都会删除这个数的末一位。当这个数只剩一位时，游戏结束。

你需要找出 Alice 用最佳方法在最后找出的最小数。

输入格式

本题有多组数据。

输入数据第一行包含一个正整数 $t$（$1 \le t \le 10^4$），表示数据组数。

接下来 $t$ 行，每行包含一个正整数 $n$（$10 \le n \le 10^9$），表示游戏中用到的这个正整数，$n$ 在十进制表示中不含前导零。

输出格式

输出 $t$ 行，每行输出一个正整数，表示游戏结束时 Alice 能得到的最小数。

输入输出样例解释

在第一个测试数据中，Alice 将 $1$ 和 $2$ 交换，然后 Bob 又将最后一位 $1$ 删除。最后得到结果 $2$。

在第二个测试数据中，Alice 将 $3$ 和 $1$ 交换，变成 $312$。然后 Bob 将最后一位 $2$ 删除，变成 $31$。接着 Alice 将 $3$ 和 $1$ 交换，变成 $13$。最后 Bob 将最后一位删除，得到最终的结果 $1$。

样例

3
12
132
487456398

2
1
3