P14835 [THUPC 2026 初赛] 又一个 01 串问题

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。 题解等资源可在 查看。

给定一个长为 $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$ 组数据的答案。以二进制形式输出。

对于第一组数据，一种最优方案为：将字符串划分为第 1、2 位的子序列和第 3、4 位的子序列，得到两个二进制数 `01` 和 `01`，其和为 $01_2 + 01_2 = 10_2$。 对于第二组数据，显然答案为 $0$。注意此时应输出 `0`，而不能输出空行。