G. 又一个 01 串问题

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

题目描述

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

输入格式

从标准输入读入数据。 包含多组数据。第一行一个正整数 T (1 ≤ T ≤ 10^5)，表示数据组数。接下来 2T 行， 每两行表示一组数据，格式如下； 第一行一个正整数 n(1 ≤ n ≤ 5 × 10^5)。 第二行一个长为 n 的 01 串。 保证 n 的总和不超过 5 × 10^5。

输出格式

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

样例

样例 1 输入

2
4
0101
3
000

样例 1 输出

10
0

样例 1 解释

对于第一组数据，一种最优方案为，将字符串划分为第 1, 4 位的子序列和第 2, 3 位 的子序列，答案为 01+01=10。 对于第二组数据，显然答案为 0。注意此时应该输出 0 而不能输出空行。