时间限制： 1.0 秒 空间限制： 512 MiB

题目描述

给定一个长为 \(n\) 的 01 串，你需要将其划分为两个子序列（可以为空），使其分别视为二进制数后的和最小。特别地，若子序列为空，则将其视为二进制数 \(0\)。以二进制形式输出这个最小的和。

输入格式

从标准输入读入数据。

包含多组数据。第一行一个正整数 \(T\)（\(1 \le T \le 10^5\)），表示数据组数。接下来 \(2T\) 行，每两行表示一组数据，格式如下：

第一行一个正整数 \(n\)（\(1 \le n \le 5 \times 10^5\)）。

第二行一个长为 \(n\) 的 01 串。

保证 \(n\) 的总和不超过 \(5 \times 10^5\)。

输出格式

输出到标准输出。

\(T\) 行，其中第 \(i\) 行包含一个整数表示第 \(i\) 组数据的答案。以二进制形式输出。

样例

样例 1 输入

2
4
0101
3
000

样例 1 输出

10
0

样例 1 解释

对于第一组数据，一种最优方案为，将字符串划分为第 \(1, 4\) 位的子序列和第 \(2, 3\) 位的子序列，答案为 \(01 + 01 = 10\)。

对于第二组数据，显然答案为 \(0\)。注意此时应该输出 \(0\) 而不能输出空行。