Description

炉石传说的新版本“狗头人与地下世界”里面法师有一张名为“惊奇套牌”的新卡牌，可以洗入牌库多张法术牌，抽到时随机选取目标释放。卡牌的费用有$0$~$9$十种。 吴瑕准备了N张卡牌，上面标有数字$0$~$9$，代表该法术牌需要耗费的法力值。吴瑕每次选取这些卡牌的最上面一张，放在已有的卡牌序列的左边或者右边。 最后这些卡牌摆成一个数字，吴瑕希望这个数字没有前导零，并且是所有摆放方法中，摆出的数最小的一种。 你能帮助吴瑕完成这个任务吗？

Input

第一行是一个数$T（T \leq 1000）$，表示有T组测试数据； 然后下面有T行， 每行是一个只含有$0$~$9$的字符串，表示$N（1 \leq N \leq 100）$张叠在一起的卡片，最左边的数字表示最上方的卡片。

Output

对于每组测试数据，请在一行内输出能得到的最小数。

Sample Input

3
565
9876543210
9876105432

Sample Output

556
1234567890
1678905432