卡利姆多的海岸被鲜血浸透，自她将父亲推入地狱的那天起，这片土地就像幽灵一样缠绕着吉安娜·普罗德摩尔。

现在，站在塞拉摩被摧毁的废墟前，她意识到自己曾经想要和平是多么天真。

聚焦之虹。这是吉安娜能想象到的最残酷、最卑劣的杀戮手段。

部落想要战争。他们会不惜一切代价摧毁我们。但如果这就是他们想要的，吉安娜很乐意给他们一场大的。

部落的战舰可以用一个仅包含 '0' 和 '1' 的字符串 $s$ 来描述，分别代表小型战舰和大型战舰。吉安娜可以对字符串施展魔法。在一次魔法中，她可以选择任意一个奇数长度的区间并将其反转。吉安娜可以根据需要多次施展此魔法。

吉安娜希望小型战舰排在前面，因为它们更容易被摧毁。她请求你的帮助，你需要告诉她她能得到的字典序最小的字符串。

注意：在本题中，假设两个序列 $s$ 和 $t$ 的长度均为 $n$，若存在一个位置 $i$ ($1 \le i \le n$)，使得对于所有 $1 \le j < i$ 都有 $s_j = t_j$，且 $s_i = '0', t_i = '1'$，则称 $s$ 的字典序小于 $t$。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。 每个测试用例仅包含一行，为一个字符串 $s$ ($|s| \le 10^5$)。

输出格式

输出一行，包含你能得到的字典序最小的字符串。

样例

输入 1

2
101001
01101100000000101010

输出 1

001011
00000000001010101111