说明

时间限制：1 Sec 内存限制：256 MB 输入文件：clean.in 输出文件：clean.out

小明得到一个二进制字符串 $s$（即字符串仅由 $0$ 和 $1$ 组成）。

在一次操作中，小明可以任意选择 $s$ 中连续的两个字符 $s_i$ 和 $s_{i+1}$，如果 $s_i$ 为 $1$ 且 $s_{i+1}$ 为 $0$，他可以删除这两个字符中的任意一个（必须删除一个，但不能两个都删除），然后字符串的长度减少 $1$。

在小明的眼中，两个不同的字符串 $x$ 和 $y$，较短的字符串更干净；如果它们长度相同，则字典序更小的字符串更干净。

小明可以对 $s$ 进行任意多次操作，使得它尽可能地干净。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来有 $t$ 行，每行为一个二进制字符串 $s$，第 $i$ 行为第 $i$ 组询问。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组的询问，为一个字符串，即能得到的最干净的字符串。

样例

样例 1

5
0001111111
0101
11001101
1110000000
1

0001111111
001
01
0
1

数据范围

$1 \le t \le 10^4$

令 $|s|$ 表示字符串 $s$ 的长度，有 $1 \le |s| \le 10^5$

题目保证所有的 $|s|$ 之和不超过 $10^5$