#include <bits/stdc++.h>
using namespace std;
#define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i = a; i < b; i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

int power(int x, unsigned int y, int p)  {  
    int res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)  
    {   if (y & 1)  
            res = (res*x) % p;
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}
vector<bool> prime(M, true);

void sieve(int n){
    for(int i = 2 ; i*i <= n ; i++){
        if(prime[i] == true){
            for(int j = i*i ; j <= n ; j += i){
                prime[j] = false;
            }
        }
    }
}
void solve(){
    int n;
    cin>>n;
    string B;
    cin>>B;
    string D = "";
    for(int i = 0 ; i < n ;i++){
        if(B[i] == '0'){
            if(D.size() == 0){
                D.pb('1');
            }
            else{
                if(D.back() == '0' || D.back() == '2')
                    D.pb('1');
                else 
                    D.pb('0');
            }
        }
        else{
            if(D.size() == 0){
                D.pb('2');
            }
            else{
                if(D.back() == '0' || D.back() == '1')
                    D.pb('2');
                else
                    D.pb('1');
            }
        }
    }
    string res = "";
    for(int i = 0 ; i < n ; i++){
        res.pb(D[i]-B[i] +'0');
    }
    cout<<res<<endl;
    return;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	#ifdef SIEVE
		sieve();
	#endif
	#ifdef NCR
		init();
	#endif
	int t=1;
	cin>>t;
	while(t--) solve();
	return 0;
}
