In the 2022 year, Mike found two binary integers a and b of length n (both of them are written only by digits 0 and 1) that can have leading zeroes. In order not to forget them, he wanted to construct integer d in the following way: 

  * he creates an integer c as a result of bitwise summing of a and b without transferring carry, so c may have one or more 2-s. For example, the result of bitwise summing of 0110 and 1101 is 1211 or the sum of 011000 and 011000 is 022000; 
  * after that Mike replaces equal consecutive digits in c by one digit, thus getting d. In the cases above after this operation, 1211 becomes 121 and 022000 becomes 020 (so, d won't have equal consecutive digits). 



Unfortunately, Mike lost integer a before he could calculate d himself. Now, to cheer him up, you want to find any binary integer a of length n such that d will be maximum possible as integer.

Maximum possible as integer means that 102 > 21, 012 < 101, 021 = 21 and so on.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains the integer n (1 ≤ n ≤ 10^5) — the length of a and b.

The second line of each test case contains binary integer b of length n. The integer b consists only of digits 0 and 1.

It is guaranteed that the total sum of n over all t test cases doesn't exceed 10^5.

Output

For each test case output one binary integer a of length n. Note, that a or b may have leading zeroes but must have the same length n.

Example

Input


5
1
0
3
011
3
110
6
111000
6
001011


Output


1
110
100
101101
101110

Note

In the first test case, b = 0 and choosing a = 1 gives d = 1 as a result.

In the second test case, b = 011 so: 

  * if you choose a = 000, c will be equal to 011, so d = 01; 
  * if you choose a = 111, c will be equal to 122, so d = 12; 
  * if you choose a = 010, you'll get d = 021. 
  * If you select a = 110, you'll get d = 121. 

We can show that answer a = 110 is optimal and d = 121 is maximum possible.

In the third test case, b = 110. If you choose a = 100, you'll get d = 210 and it's the maximum possible d.

In the fourth test case, b = 111000. If you choose a = 101101, you'll get d = 212101 and it's maximum possible d.

In the fifth test case, b = 001011. If you choose a = 101110, you'll get d = 102121 and it's maximum possible d.
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main
{
    /*static class Pair{
        int key;
        int value;
 
        Pair(int key,int value)
        {
            this.key=key;
            this.value=value;
        }
    }
        public static class SortbyKey implements Comparator<Pair>
        {
            public int compare(Pair a, Pair b){
            return (a.key- b.key); 
        }*/
    
 
    public static void process()throws IOException
    {
     int n=ni();
     String b=nn();
     
     String a="1";
     char d='1';
     if(b.charAt(0)=='1')
        d='2';
    

     for(int i=1;i<n;i++)
     {
        if(b.charAt(i)=='1')
        {
            if(d=='1'||d=='0')
                {a+="1";d='2';}
            else if(d=='2')
                {a+="0";d='1';}
            
        }
        else
        {
            if(d=='1')
            {a+="0";d='0';}
          else
            {a+="1";d='1';}
        }
     }
     pn(a);
    }
     
    
    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new AnotherReader();
        boolean oj = true;
         //PrintWriter out=new PrintWriter("output");
        //oj = System.getProperty("ONLINE_JUDGE") != null;
        //if(!oj) sc=new AnotherReader(100);
 
     //int i=1;
 int T=ni(); 
 
 while(T-->0)
      {
      // p("Case #"+i+": ");
            process();
            //i++;
      }
        long s = System.currentTimeMillis();
      
        out.flush();
        if(!oj)
            System.out.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }
    static void sort(long arr[],int n)
    {
    shuffle(arr,n);
    Arrays.sort(arr);
    }
    static void shuffle(long arr[],int n)
    {
        Random r=new Random();
        for(int i=0;i<n;i++)
        {
          long temp=arr[i];
          int pos=i+r.nextInt(n-i);
          arr[i]=arr[pos];
          arr[pos]=temp;
        }
    }
 
    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static String nn()throws IOException{return sc.next();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static long bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static int[] iarr(int N)throws IOException{int[]ARR=new int[N];for(int i=0;i<N;i++){ARR[i]=ni();}return ARR;}
    static long[] larr(int N)throws IOException{long[]ARR=new long[N];for(int i=0;i<N;i++){ARR[i]=nl();}return ARR;}
    static boolean multipleTC=false;
            
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////
    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
 
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
 