Lee 正在为聚会打扫房子,这时他在地毯下发现了一根凌乱的绳子。现在他想以一种时尚的方式准确地清洁它......
他找到的字符串 $$$s$$$ 是长度为 $$$n$$$ 的二进制字符串(即字符串仅由 0 和 1 组成)。
他一步可以选择两个连续的字符$$$s_i$$$和$$$s_{i+1}$$$,如果$$$s_i$$$为1且$$$s_{i + 1}$$$为0,他可以恰好删除其中一个(他可以选择删除哪一个,但不能同时删除两个字符)。擦除后字符串会收缩。
Lee 可以进行任意数量的移动(可能为零),并且他希望使字符串 $$$s$$$ 尽可能干净。他认为对于两个不同的字符串 $$$x$$$ 和 $$$y$$$,较短的字符串更干净,如果它们的长度相同,那么按字典顺序较小的字符串更干净。
现在你应该回答 $$$t$$$ 测试用例:对于第 $$$i$$$ 个测试用例,打印 Lee 通过执行一定次数的移动可以获得的最干净的字符串。
小提醒:如果我们有两个长度相同的字符串 $$$x$$$ 和 $$$y$$$,那么 $$$x$$$ 按字典顺序小于 $$$y$$$ 如果有一个位置 $$$i$$$ 使得 $$$x_1 = y_1$$$, $$$x_2 = y_2$$$,..., $$$x_{i - 1} = y_{i - 1}$$$ 且 $$$x_i < y_i$$$。
输入
第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
接下来的 $$$2t$$$ 行包含测试用例 - 每两行一个。
每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$s$$$ 的长度。
第二行包含二进制字符串$$$s$$$。字符串 $$$s$$$ 是长度为 $$$n$$$ 的字符串,仅由零和一组成。
保证测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
打印 $$$t$$$ 答案 — 每个测试用例一个。
第 $$$i$$$ 测试用例的答案是 Lee 在进行一定次数的移动(可能为零)后可以获得的最干净的字符串。
示例
输入 #1
5 10 0001111111 4 0101 8 11001101 10 1110000000 1 1
输出 #1
0001111111 001 01 0 1
注意
在第一个测试用例中,Lee 无法执行任何动作。
在第二个测试用例中,Lee 应该删除 $$$s_2$$$。
在第三个测试用例中,Lee 可以按照以下顺序进行移动: 11001101 $$$\rightarrow$$$ 1100101 $$$\rightarrow$$$ 110101 $$$\rightarrow$$$ 10101 $$$\rightarrow$$$ 1101 $$$\rightarrow$$$ 101 $$$\右箭头$$$ 01。