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

你删我也删

题目描述

乐柠兔和许老师得到一个长度为 $n$ 的二进制字符串 $s$。

保证字符串 $s$ 中至少包含一个字符 0，也至少包含一个字符 1。

两人依次进行一次操作：

1. 乐柠兔先选择字符串中的一个 0 并删除；
2. 许老师再从删除后的字符串中选择一个 1 并删除。

乐柠兔希望最终得到的字符串字典序尽可能大，而许老师希望最终得到的字符串字典序尽可能小。

两人都会采用最优策略。

请输出双方最优策略下最终得到的字符串。

对于两个长度相同且不同的字符串，如果在第一个不同的位置上，字符串 $A$ 的字符更小，则称 $A$ 的字典序更小。

输入格式

第一行输入一个整数 $T$，表示测试用例数量。

接下来 $T$ 行，每行输入一个二进制字符串 $s$。

输出格式

对于每组测试数据，输出一行最终得到的字符串。

样例

样例输入

4
101
11001
0010
0101010000010100100101

样例输出

1
101
00
01010000010100100101

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le T\le100$；
• $3\le |s|\le100$；
• $s$ 只包含字符 0 和 1；
• $s$ 中至少包含一个 0，也至少包含一个 1。

本题共设置 $20$ 个测试点。

特殊性质 A

字符串形如若干个 0 后接若干个 1。

特殊性质 B

字符串形如若干个 1 后接若干个 0。