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.io.File;
	
	import java.io.FileNotFoundException;
	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.FileReader;
	import java.io.FileWriter;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.InputStreamReader;
	import java.io.PrintWriter;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Calendar;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Scanner;
	import java.util.Set;
	import java.util.StringTokenizer;
	
	
	public class D {
		static int mx= 1000005;
		static List<String> insure=new ArrayList<>();
		static MScanner in = new MScanner(System.in);
	
		static int merge(int[]a,int[] temp, int left, int mid, int right) {
			int inv=0;
			int i=left;
			int j=mid+1;
			int k=left;
			
			while(i<=mid && j<=right) {
				if(a[i]<=a[j])temp[k++]=a[i++];
				else{
					temp[k++]=a[j++];
					inv+=(mid-i+1);
				}
			}
			while(i<=mid) {
				temp[k++]=a[i++];
			}
			for(int m=left;m<=right;++m) {
				a[m]=temp[m];
			}
			return inv;
		}

		static void solve() throws Exception{
			MScanner sc = new MScanner(System.in);
			int n=s.nextInt();
			String a= s.next();
			String b="";
			StringBuilder ans = new StringBuilder();
			int last=0;
			for(int i=0;i<n;++i) {
				int chara=(int)a.charAt(i)-'0';
				int v = chara+1;
				if(last!=v) {
					ans.append('1');
					last=chara+1;
				}
				else{ans.append('0');
					last=chara;
				}
			}
			pw.println(ans);
			
		}
		
		public static void main(String[] args) throws Exception {
			s = new MScanner(System.in);
			pw = new PrintWriter(System.out);
			int tc = 1;
			tc	=s.nextInt();
			for (int test = 1; test <= tc; test++) {
				solve();
			}
			pw.flush();
		}
	
		static Integer[] sort(Integer[] arr,int n) {
			Arrays.sort(arr, new Comparator<Integer>() {
	            @Override
	            public int compare(Integer arg0, Integer arg1)
	            {
	                 // TODO Auto-generated method stub
	                int c1 = Integer.bitCount(arg0);
	                int c2 = Integer.bitCount(arg1);
	                if (c1 <= c2)
	                    return 1;
	                else
	                    return -1;
	            }
	        });
	        return arr;
		}
	
		public static Integer[] inputI(int n) throws IOException{
			Integer[] a = new Integer[n];
			for (int i = 0; i < n; i++)
				a[i] = in.nextInt();
			return a;
		}
		public static int[][] imat(int n,int m) throws IOException{
			int[][] a = new int[n][m];
			for (int i = 0; i < n; i++) {
				for(int j=0;j<m;j++) {
					a[i][j]=s.nextInt();
				}
			}
			return a;
		}
		static int kadane(int A[])
		{
			int lsum=A[0],gsum=A[0];
			for(int i=1; i<A.length; i++)
			{
				lsum=Math.max(lsum+A[i],A[i]);
				gsum=Math.max(gsum,lsum);
			}
			return gsum;
		}
		static void print(int A[])
		{
			for(int i:A)System.out.print(i+" ");
			System.out.println();   
		}
	 
		static void print(Integer A[])
		{
			for(int i:A)System.out.print(i+" ");
			System.out.println();   
		}
		static void print(long A[])
		{
			for(long i:A)System.out.print(i+ " ");
			System.out.println();
	 
		}
		static void print(boolean A[])
		{
			for(boolean i:A)System.out.print(i+ " ");
			System.out.println();
	 
		}
	//	static void sort(long[] a) 
	//	{
	//		ArrayList<Long> l=new ArrayList<>();
	//		for (long i:a) l.add(i);
	//		Collections.sort(l);
	//		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	//	}
	// 
		static String swap(String X,int i,int j)
		{
			char ch[]=X.toCharArray();
			char a=ch[i];
			ch[i]=ch[j];
			ch[j]=a;
			return new String(ch);
		}
		
		static void sort(int[] a) {
			ArrayList<Integer> l=new ArrayList<>();
			for (int i:a) l.add(i);
			Collections.sort(l);
			for (int i=0; i<a.length; i++) a[i]=l.get(i);
		}
		static boolean isPrime(long N)
		{
			if (N<=1)  return false; 
			if (N<=3)  return true; 
			if (N%2 == 0 || N%3 == 0) return false; 
			for (int i=5; i*i<=N; i=i+6) 
				if (N%i == 0 || N%(i+2) == 0) 
					return false; 
			return true; 
		}
		static int i() throws IOException
		{
			return in.nextInt();
		}
	 
		static long l() throws IOException
		{
			return in.nextLong();
		}
		static int[] input(int N) throws IOException{
			int A[]=new int[N];
			for(int i=0; i<N; i++)
			{
				A[i]=in.nextInt();
			}
			return A;
		}
	 
		static long[] inputLong(int N) throws IOException     {
			long A[]=new long[N];
			for(int i=0; i<A.length; i++)A[i]=in.nextLong();
			return A;
		}
		
		static void preComp_Prime() throws Exception{//To precompute prime numbers
			int[] a = new int[mx];
			int[] ans = new int[mx];
			Arrays.fill(a, 1);
			a[0]=0;
			a[1]=0;
			for(int i=2;i*i<=1000000;i++) {
				for(int j=i*i;j<=1000000;j+=i) {
					a[j]=0;
				}
			}//precomp done
			for(int i=2;i<=1000000;i++) {//Checking if the sum of 2 primes is a prime or not
				if(a[i]==1 && a[i-2]==1)ans[i]=1;
				ans[i]+=ans[i-1];
			}
		}
	
		
		static int gcd(int a,int b) {
			if(a==0)return b;
			return gcd(b%a,a);
		}
		
	
		
		static PrintWriter pw;
		static MScanner s;
		static class MScanner {
			StringTokenizer st;
			BufferedReader br;
			public MScanner(InputStream system) {
				br = new BufferedReader(new InputStreamReader(system));
			}
		 	public MScanner(String file) throws Exception {
				br = new BufferedReader(new FileReader(file));
			}
		 
			public String next() throws IOException {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(br.readLine());
				return st.nextToken();
			}
			public int[] intArr(int n) throws IOException {
				int[] in = new int[n];
				for (int i = 0; i < n; i++)
					in[i] = nextInt();
				return in;
			}
			public void pArr(int[] in,int n) throws IOException {
				
				for (int i = 0; i < n; i++)
					System.out.println(in[i]);
				
			}
			public void pLis(ArrayList<Integer> l) throws IOException {
				
				for (int i = 0; i < l.size(); i++)
					System.out.println(l.get(i));
				
			}
		 	public long[] longArr(int n) throws IOException {
				long[] in = new long[n];
				for (int i = 0; i < n; i++)
					in[i] = nextLong();
				return in;
			}
			public int[] intSortedArr(int n) throws IOException {
				int[] in = new int[n];
				for (int i = 0; i < n; i++)
					in[i] = nextInt();
				shuffle(in);
				Arrays.sort(in);
				return in;
			}
			public long[] longSortedArr(int n) throws IOException {
				long[] in = new long[n];
				for (int i = 0; i < n; i++)
					in[i] = nextLong();
				shuffle(in);
				Arrays.sort(in);
				return in;
			}
		 	public Integer[] IntegerArr(int n) throws IOException {
				Integer[] in = new Integer[n];
				for (int i = 0; i < n; i++)
					in[i] = nextInt();
				return in;
			}
			public Long[] LongArr(int n) throws IOException {
				Long[] in = new Long[n];
				for (int i = 0; i < n; i++)
					in[i] = nextLong();
				return in;
			}
			public String nextLine() throws IOException {
				return br.readLine();
			}
			public int nextInt() throws IOException {
				return Integer.parseInt(next());
			}
			public double nextDouble() throws IOException {
				return Double.parseDouble(next());
			}
			public char nextChar() throws IOException {
				return next().charAt(0);
			}
			public long nextLong() throws IOException {
					return Long.parseLong(next());
			}
		 	public boolean ready() throws IOException {
					return br.ready();
			}
			public void waitForInput() throws InterruptedException {
					Thread.sleep(3000);
			}
		}
			static void shuffle(int[] in) {
				for (int i = 0; i < in.length; i++) {
					int idx = (int) (Math.random() * in.length);
					int tmp = in[i];
					in[i] = in[idx];
					in[idx] = tmp;
				}
		}
		 	static void shuffle(long[] in) {
		 		for (int i = 0; i < in.length; i++) {
					int idx = (int) (Math.random() * in.length);
					long tmp = in[i];
					in[i] = in[idx];
					in[idx] = tmp;
				}
			}
	}
	
