#include <bits/stdc++.h>
using namespace std;

int main() {
	
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	  string b;
	  cin>>n;
	  cin>>b;
	  string d="";
	  string a="";
	  if(b[0]=='0')
	  {
	      a="1";
	      d="1";
	  }
	  else{
	      a="1";
	      d="2";
	  }
	  for(auto i=1; i<n; i++)
	  {
	     if(b[i]=='0')
	     {
	         if(d[i-1] == '1')
	         {
	             a+="0";
	             d+="0";
	         }
	         else{
	             a+="1";
	             d+="1";
	         }
	     }
	    else if(b[i]=='1')
	     {
	         if(d[i-1]=='2')
	         {
	             a+="0";
	             d+="1";
	         }
	         else{
	             a+="1";
	             d+="2";
	         }
	     }
	  }
	  cout<<a<<endl;
	}
	return 0;
}
