给你一个由 0 和 1 组成的字符串 $$$s$$$。您可以执行以下操作:
- 选择 $$$s$$$ 中包含相同数量的 0 和 1 的非空连续子字符串;
- 翻转子字符串中的所有字符,即将所有 0 替换为 1,反之亦然;
- 反转子字符串。
例如,考虑 $$$s$$$ = 00111011,以及以下操作:
- 选择前六个字符作为要操作的子字符串:00111011。请注意,0 和 1 的数量相等,因此这是合法的选择。选择子字符串 0、110 或整个字符串是不可能的。
- 翻转子字符串中的所有字符:11000111。
- 反转子字符串:10001111。
查找在零次或多次操作后可以从 $$$s$$$ 获得的按字典顺序最小的字符串。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \leq T \leq 5 \cdot 10^5$$$) — 测试用例的数量。以下每行 $$$T$$$ 都包含一个非空字符串 - 相应测试用例的输入字符串 $$$s$$$。
所有字符串均由字符0和1组成,其总长度不超过$$$5 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上打印在零次或多次操作后可以从 $$$s$$$ 获得的按字典顺序排列的最小字符串。
示例
输入 #1
3 100101 1100011 10101010
输出 #1
010110 0110110 10101010
注意
在第一个测试用例中,应将单个操作应用于整个字符串。
在第二个测试用例中需要两次操作:0111001、0110110。
在第三个测试用例中,字符串在任何操作后都保持不变。