根据观察得到的一些规律（？）

引理一：设组成答案的两个数在二进制下分别是 $x, y$，那么 $x$ 一定由且仅由一段前缀所有的 $1$ 组成，$y$ 是一坨前导 $0$ 和剩下部分组成。

比如以下样例：

10110100

那么 $x = 111, y=(00)100$。

定义分界点 $p$ 表示 $[1,p]$ 这段前缀里所有的 $1$ 都在 $x$ 里，而 $[1, p]$ 里面所有的 $0$ 以及 $(p, n]$ 这段后缀都在 $y$。

设 $size(x), size(y)$ 表示去除前导 $0$ 后，$x, y$ 的长度。

引理二：考虑从前往后枚举分界点，枚举到第一个 $size(x) \ge size(y)$ 的分界点，此时的 $x, y$ 即为答案。

让我想想怎么证明 2333.

::::info[来自deepseek]

一、最优解的结构

引理1：存在一个最优划分，使得其中一个数（记为 $x$）恰好由原串某个前缀 $[1, p]$ 中的所有 1 按顺序组成，而另一个数（记为 $y$）由该前缀中的所有 0 以及后缀 $(p, n]$ 的全部字符按顺序组成。

简要证明：考虑任意最优划分，得到两个数 $a$ 和 $b$（不妨设 $a \le b$）。设 $j$ 为 $b$ 的最高有效位在原串中的位置。则所有在 $j$ 之前的 1 都必须分配给 $a$（否则，若某个 $i < j$ 且 $s_i = 1$ 分配给了 $b$，则 $i$ 会成为 $b$ 的最高有效位，与 $j$ 的定义矛盾）。进一步，可以通过交换调整使得 $a$ 仅包含这些 1，且不增加和。详细论证可通过反证法或交换差值的分析完成。

二、确定最优分界点 $p$

对于形如上引理的划分，设 $k$ 为前缀 $[1, p]$ 中 1 的个数（即 $x$ 的有效长度），$L$ 为 $y$ 去除前导零后的有效长度。令 $F(p) = x(p) + y(p)$，其中 $x(p) = 2^k - 1$，$y(p)$ 为后缀 $[p+1, n]$ 的二进制值。

当 $p$ 增加时（仅考虑 $s_{p+1} = 1$ 的情形，因为 $s_{p+1} = 0$ 时 $F(p)$ 不变），计算 $F(p+1) - F(p)$ 可得：

其中 $L = n - p$（因为此时 $s_{p+1}=1$，故 $y$ 的有效长度即为后缀长度）。因此：

• 若 $k < L-1$，则 $\Delta < 0$，和随 $p$ 增加而减小；
• 若 $k = L-1$，则 $\Delta = 0$，和不变；
• 若 $k \ge L$，则 $\Delta > 0$，和随 $p$ 增加而增大。

故 $F(p)$ 在 $k \ge L$ 时开始单调不减，最小值出现在第一个满足 $k \ge L$ 的 $p$ 处（或与之等价的 $k = L-1$ 的最后一个 $p$，但两者对应的和相同）。

三、算法实现

根据以上分析，算法步骤如下：

1. 预处理数组 $f(i)$，表示从位置 $i$ 开始的后缀去除前导零后的有效长度。
2. 初始化 $cnt = 0$，从 $p = 0$ 开始枚举：
   • 若 $cnt \ge f(p+1)$，停止，当前 $p$ 即为最优分界点。
   • 否则，令 $p := p+1$，若 $s_p = 1$ 则 $cnt := cnt + 1$。
3. 计算 $x = 2^{cnt} - 1$（即 $cnt$ 个 1 的二进制数），$y$ 为后缀 $s[p+1..n]$ 的二进制值。
4. 输出 $x + y$ 的二进制表示。

该算法时间复杂度为 $O(n)$，可处理大规模输入。

::::

很遗憾没能看懂。那让我说点人话吧。这之前大家可以手玩一下样例，以便更好地理解。

证明引理一：

考虑现在的 $x$ 存在一部分前导 $0$，这时候答案显然不变，不需要考虑。

考虑现在的 $x$ 中间掺杂了一些 $0$，而 $y$ 的结构不变。这种情况会使 $x$ 的位数变多，$x+y$ 显然更大，也不优。

证明引理二：

大家都知道：设二进制数 $a, b$ 的位数分别为 $size(a), size(b)$，则 $size(a+b) \le \max(size(a), size(b))+1$.

所以我们一定要让 $a, b$ 的位数尽可能接近（注意 $b$ 要除去前导 $0$）。

考虑调整法证明。不妨将 $x$ 中最后一个 $1$ 放到 $y$ 里，大致有以下两种情况：

发现后者答案一定是不优于前者的。

::::success[code]

#include <bits/stdc++.h>
#define gt getchar
#define pt putchar

typedef long long ll;
const int MAXN = 1e6 + 5;

ll read() {
    ll x = 0, f = 1;char ch = gt();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = gt();}
    while (ch >= '0' && ch <= '9') {x *= 10;x += ch - '0';ch = gt();}
    return x * f;
}

void ckmax(ll &a, ll b) {a = std::max(a, b);}
void ckmax(double &a, double b) {a = std::max(a, b);}
void ckmin(ll &a, ll b) {a = std::min(a, b);}
void ckmin(double &a, double b) {a = std::min(a, b);}

std::string s, a, b;
ll ans[MAXN];

void solve() {
	ll n = read();
	std::cin >> s;
	s = " " + s;
	for (int i = 0; i <= n + 1; i++)
		ans[i] = 0;
	a = "", b = "";
	ll nxt;
	for (int i = 1; i <= n; i = nxt) {
		//不断跳到下一个 1 的位置 
		if(s[i] == '1') {
			a += s[i];//a 存的是前缀里面所有的 1 
			int j;
			for (j = i + 1; j <= n; j++) {
				if(s[j] == '1')
					break;
			}
			// 找到下一个 1 
			nxt = j;
			if(nxt > n)
				break;
			if(a.size() >= n - nxt + 1) {
				// 如果满足引理二的条件 
				b = s.substr(nxt, n - nxt + 1);//取出后半段所有的数字 
				break;
			}
		}
		else
			nxt = i + 1;
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	//翻转方便计算 
	ll m = 0;
	for (int i = 0; i < std::max(a.size(), b.size()); i++) {
		ll p = 0, q = 0;
		if(i < a.size()) {
			p = a[i] - '0';
		}
		if(i < b.size()) {
			q = b[i] - '0';
		}
		ans[i] += p + q;
		ans[i + 1] += ans[i] / 2;
		ans[i] %= 2;
		m = i;
	}
	//二进制加法 
	while(ans[m + 1])
		++m;
	//希望大家不要像我把 while 写成 if 
	for (int i = m; i >= 0; i--)
		std::cout << ans[i];
	std::cout << '\n';
}

int main() {
	ll T = read();
	while(T--)
		solve();
	return 0;
}

::::