该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

进入到集训队只是第一步，想要在比赛中斩获佳绩就需要勤加练习，头悬梁锥刺股卧薪尝胆（？）（没有那么夸张，不过每天还是要认真做题的）

那么是时候介绍几个常见的网络竞赛平台了，实际上在一贴通里都有介绍，但在这里会写的更详细一点。

国外平台 Codeforces（https://codeforces.com）：全世界最大的OJ，周期性举办大量优质赛事，并且还会上线往年各种比赛的练习。是ACM生涯中必然会接触，也必须要在上面进行大量学习的平台。

让人又爱又恨的是这个平台它有 Cloudflare 防 DDoS，每次比赛的时候就会出现像上图的“验证你是否是真人”的情况。会耽误一些做题时间。（比如这段介绍就是笔者在被卡了 20 分钟以后彻底不想打比赛了来写的）

国外平台 Atcoder（https://atcoder.jp）：日本最大的OJ，全世界第二大（也许是）的OJ。提供三种区分度比较高的比赛，其ABC难度比较适合新手快速学习大量常用算法和解题思路。比较具有教育意义。

它没有 Cloudflare。并且它的题目真的很适合初学一个算法的时候进行巩固。

国内平台洛谷（https://luogu.com）：国内最大OJ，可惜面向群体更加偏向于OI竞赛生而非ACM生，所以上面的题目多而杂，如果想要进行练习，推荐在有一定算法基础后刷上面的用户题单-全面提升题单。

国内平台牛客（https://ac.nowcoder.com）：

: 今晚 7 点，牛客周赛/小白月赛/练习赛 ..... @全体成员

: TD

牛客和 atcoder 坐一桌。这个平台的大部分公开赛题目也是更适合新手入门，或者巩固某些知识点。比 atcoder 好的一点是牛客是中文的并且比赛时间略早一点。（虽然大家一般打完牛客以后晚上会接着打 codeforces）

如果你从本题第一行仔仔细细看到了这里，那么恭喜你，我要额外告诉你一个小知识：题目背景一般与题目内容只有关联性，但完全不看题目背景并不会影响解题。你可以在解完所有题目以后，再折回来了解大学里可以打的丰富多彩的比赛。或者是比完赛再看也行。快点开题吧！

题目描述

小鹿正在打 Codeforces，但他被 Cloudflare 验证拦下来了。Cloudflare 要求他回答一个问题以继续。问题是这样的。

给定一个正整数。你可以操作若干次（可以为0次），交换这个正整数两个不同位置上的数，要求最后获得的正整数尽可能小。

请你帮助他输出这个最小值。

请注意：这个数的最高位不能为0，否则不是合法的正整数。

输入格式

本题包含多组测试数据，第一行输入一个整数 $T(1 \leq T \leq 100)$，代表测试数据组数。

对于每组数据：输入一行，包含一个整数 $N(1 \leq N \leq 10^9)$。

输出格式

每组测试数据输出独立的一行，包含答案。

样例

2
201094
23456

100249
23456

注意：001249不是合法的正整数。