题目背景

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2026pre 查看。

题目描述

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

输入格式

从标准输入读入数据。

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

• 第一行一个正整数 $n$（$1 \leq n \leq 5 \times 10^5$）。
• 第二行一个长为 $n$ 的 01 串。

保证所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

输出到标准输出。

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

2
4
0101
3
000

10
0

提示

对于第一组数据，一种最优方案为：将字符串划分为第 1、2 位的子序列和第 3、4 位的子序列，得到两个二进制数 01 和 01，其和为 $01_2 + 01_2 = 10_2$。

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