救救孩子吧 必关

#include<bits/stdc++.h>
using namespace std;
string s,ans1,ans2,ans3;
int nxt[500010],pre[500010];
string sum(string sa,string sb)
{
	//cout<<sa<<" "<<sb<<endl;
	if(sa.length()<sb.length())swap(sa,sb);
	string ans;
	bool flag=0,x,y;
	for(int i=sa.length()-1;i>=0;i--)
	{
		if(i<sa.length()-sb.length())y=0;
		else if(sb[i-(sa.length()-sb.length())]=='1')y=1;
		else y=0;
		if(sa[i]=='1')x=1;
		else x=0;
		if((!x)&&(!y))
		{
			if(flag)ans="1"+ans;
			else ans="0"+ans;
			flag=0;
		}
		else if(((!x)&&y)||(x&&(!y)))
		{
			if(flag)ans="0"+ans,flag=1;
			else ans="1"+ans,flag=0;
		}
		else
		{
			if(flag)ans="1"+ans;
			else ans="0"+ans;
			flag=1;
		}
		//cout<<ans<<" "<<x<<" "<<y<<" "<<flag<<endl;
	}
	if(flag)ans="1"+ans;
	while(ans.length()>1&&ans[0]=='0')ans.erase(0,1);
	return ans;
}
string cmp(string sa,string sb)
{
	if(sa.length()>sb.length())return sb;
	if(sa.length()<sb.length())return sa;
	for(int i=0;i<sa.length();i++)
	{
		if(sa[i]>sb[i])return sb;
		if(sa[i]<sb[i])return sa;
	}
	return sa;
}
int main()
{
//	freopen("data.out","r",stdin);
//	freopen("THUPC.out","w",stdout);
	int t,n,p,fi,x,y,a,b,c;
	bool flag;
	cin>>t;
	while(t--)
	{
		cin>>n>>s;
		p=-1;
		for(int i=0;i<n;i++)
		{
			if(s[i]=='1')
			{
				if(p!=-1)nxt[p]=i;
				if(p==-1)fi=i;
				pre[i]=p;
				p=i;
			}
		}
		if(p==-1)
		{
			cout<<"0"<<endl;
			continue;
		}
		nxt[p]=-1;
		flag=0;
		for(int i=fi;i!=-1;i=nxt[i])
		{
			x=i-fi+1;
			if(nxt[i]!=-1)y=n-nxt[i];
			else y=0;
			if(x==y)
			{
				flag=1;
				a=pre[i];
				b=i;
				c=nxt[i];
				break;
			}
			if(x>y)
			{
				a=pre[i];
				b=i;
				break;
			}
		}
		if(flag)
		{
			if(a!=n-1)ans1=sum(s.substr(0,a+1),s.substr(a+1,n-(a+1)));
			else ans1=sum(s,"");
			if(b!=n-1)ans2=sum(s.substr(0,b+1),s.substr(b+1,n-(b+1)));
			else ans2=sum(s,"");
			if(c!=n-1)ans3=sum(s.substr(0,c+1),s.substr(c+1,n-(c+1)));
			else ans3=sum(s,"");
			cout<<cmp(ans1,cmp(ans2,ans3))<<endl;
		}
		else
		{
			if(a!=n-1)ans1=sum(s.substr(0,a+1),s.substr(a+1,n-(a+1)));
			else ans1=sum(s,"");
			if(b!=n-1)ans2=sum(s.substr(0,b+1),s.substr(b+1,n-(b+1)));
			else ans2=sum(s,"");
			//cout<<ans1<<" "<<ans2<<endl;
			cout<<cmp(ans1,ans2)<<endl;
		}
	}
	return 0;
}