题解

# include<iostream>
# include<algorithm>
using namespace std;
void f(){
	int n,a[100003]={0},b[100003]={0},d[100003]={0},f[3];
	char c[100003];
	cin>>n>>c;
	for(int i=0;i<n;++i){
		fill(f,f+3,1);
		b[i]=c[i]-48;
		if(i==0) a[i]=1;
		else{
			if(b[i]==0) f[2]=0;
			else f[0]=0;
			f[d[i-1]]=0;
			for(int j=2;j>=0;--j){
				if(f[j]){
					a[i]=j-b[i];
					break;
				} 
			}
		}
		d[i]=a[i]+b[i];
		cout<<a[i];
	}
	cout<<endl;
}
int main(){
	int t;
	cin>>t;
	for(int i=0;i<t;++i) f();
	return 0;
}