Description

经过小D的加油助威，他心爱的小松鼠终于拿到了阵法中全部的无尽能源，而且小松鼠还把所有太空海盗小兵揍了一顿。太空海盗的老大哥就坐不住了，立马发挥出他的枭雄本色，死道友不死贫道，直接坐船逃跑临走前还把他们老巢中剩下的所有无尽能源引爆了。在老巢里还年幼无知的小D可就倒了大霉了，无尽能源的爆炸将他炸的起飞。经过一段时间，小D从晕厥中醒来，看向四周，眉头紧皱“我，我为什么看不到了?！”
小D的眼睛瞎了，他的两个小弟就想找个办法让他走出阴影，他们就找来了一些题，来分散注意力。
但小D却并没有闷闷不乐，他被炸飞的时候可没有松手，带回来了大部分的无尽能源，足以富足过完余生，不过为了不寒了小弟们的心，他还是配合了起来。

小弟把题目念给瞎子小D听：

你有一个由0到9的数字组成的字符串。您可以执行以下操作任意（可以是0）次:

• 你可以选择一个位置，删除第个位置上的一个数字。然后在任何位置插入数字(在开头、结尾或任何两个相邻数字之间)。

通过执行这些操作，你能得到的字典上最小 的字符串是什么？

当且仅当下列条件成立时，字符串在字典序上小于相同长度的字符串:

• 在和不同的第一个位置，字符串的数字比中相应的数字小。

作为拥有两个小第的老大来说，小D肯定可以对答如流。

Format

Input

第一行包含一个整数——题目的数量。

每个题目由包含一个字符串的单行组成，该字符串由数字组成。请注意，s只是一个由数字组成的字符串，所以允许前导。

Output

每道题目输出单个字符串—可能获得的最小字符串。

Samples

4
04829
9
01
314752277691991

02599
9
01
111334567888999

Hint

表示字符串的长度