
#include <bits/stdc++.h> 
using namespace std; 
#define ll                  long long int
#define rep(i,k,n)          for(int i=k;i<n;i++)
#define pb                  push_back  
#define mp                  make_pair
#define fi                  first
#define se                  second
#define vi                  vector <ll>
#define all(x)              x.begin(), x.end()
#define clr(x)              memset(x, 0, sizeof(x))
#define sortall(x)          sort(all(x))
#define fill(a,b)           memset(a, b, sizeof(a))
#define deb(x)              cout << #x << "=" << x << endl
#define deb2(x, y)          cout << #x << "=" << x << "," << #y << "=" << y << endl
#define fast_io             ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define show(v)             rep(i,0,v.size()) cout<<v[i]<<" "; cout<<endl;
 
const int mod = 1000000007;
 
 
int main()
{
	
	ll tc = 1;
	cin>>tc;
	while(tc--)
	{
		ll n;
		cin>>n;
		string b;
		cin>>b;
		string a = "1";
		string d;
		if(b[0] == '0') d = "1";
		else d = "2";
		rep(i,1,n)
		{
			if(d[i-1] == '1')
			{
				if(b[i] == '1')
				{
					a+= '1';
					d+= '2';
				}
				else 
				{
					a += '0';
					d += '0';
				}
			}
			else if(d[i-1] == '0')
			{
				if(b[i] == '0')
				{
					a += '1';
					d += '1';
				}
				else
				{
					a += '1';
					d += '2';
				}
			}
			else if(d[i-1] == '2')
			{
				
				if(b[i] == '0')
				{
					a += '1';
					d += '1';
				}
				else
				{
					a += '0';
					d+= '1';
				}
			}
		}
		cout<<a<<endl;
	}
 
	return 0;
}
	