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.*;
import java.util.*;

public class Solution {
	static final int M = 1000000007;

	// fast scanner template
	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long[] readarrayLong(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] readarrayInt(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}

	// sorting template
	static void sortLong(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 void sortInt(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 class Graph {
		private LinkedList<Integer> adj[];
		public String s;
		public String dpch;

		Graph(int n) {
			adj = new LinkedList[n];
			for (int i = 0; i < n; i++) {
				adj[i] = new LinkedList<>();
			}
		}

		void addEdges(int u, int v) {
			adj[u].add(v);
		}

		int dfsUtil(int v, boolean[] vis) {
			int count = 0;
			vis[v] = true;
			Stack<Integer> stack = new Stack<>();
			stack.push(v);
			while (stack.empty() == false) {
				int x = stack.peek();
				stack.pop();
				if (vis[x] != true) {
					vis[x] = true;
					if (this.s.charAt(x) == this.dpch.charAt(0)) {
						count++;
					}
				}
				Iterator<Integer> it = adj[x].listIterator();
				while (it.hasNext()) {
					int n = it.next();
					if (!vis[n])
						stack.push(n);
				}
			}
			return count;
		}
	}

	static class Pair<F, S> {
		F first;
		S second;

		Pair(F first, S second) {
			this.first = first;
			this.second = second;
		}

		public F getFirst() {
			return this.first;
		}

		public S getSecond() {
			return this.second;
		}
		// Sort on basis of first term, reverse p1.first and p2.first to sort in desc
		// Collections.sort(a, (p1, p2) -> (p1.first - p2.first));

		// Sort on the basis of second term, reverse p1.second and p2.second to sort in
		// desc
		// Collections.sort(a, (p1, p2) -> (p1.second - p2.second));
	}

	static int __gcd(int a, int b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);
	}

	public static FastScanner fs = new FastScanner();

	// main code
	public static void main(String[] args) throws IOException {
		int t = fs.nextInt();
		StringBuilder res = new StringBuilder();
		while (t-- > 0) {
			int n = fs.nextInt();
			char[] ch = fs.next().toCharArray();
			int sum = (ch[0] - '0') + 1;
			res.append(1);
			for (int i = 1; i < ch.length; i++) {
				if (sum == 2) {
					if (ch[i] == '1') {
						res.append(0);
						sum = 1;
					} else {
						res.append(1);
						sum = 1;
					}
				} else if (sum == 1) {
					if (ch[i] == '1') {
						res.append(1);
						sum = 2;
					} else {
						res.append(0);
						sum = 0;
					}
				}
				else {
					if (ch[i] == '1') {
						res.append(1);
						sum = 2;
					} else {
						res.append(1);
						sum = 1;
					}
				}
			}
			res.append("\n");
		}
		System.out.println(res);
	}

}
