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.math.BigInteger;
import java.util.*;
import static java.lang.Math.PI;
import static java.lang.System.in;
import static java.lang.System.out;
import static java.lang.System.err;

public class B {  
    public static void main(String[] args) throws Exception {   
        Foster sc = new Foster();
        PrintWriter p = new PrintWriter(out);
        int t = sc.nextInt();
        while(t--!=0){
            int n = sc.nextInt();
            String str = sc.next();
            int a[] = new int[n];
            int b[] = new int[n];
            for(int i = 0; i < n; i++){
                if(str.charAt(i)=='1')  b[i] = 1;
                else    b[i] = 0;
            }
            a[0] = 1;
            int prev = a[0] + b[0];
            for(int i = 1; i < n; i++){
                if(prev==2){    // cur = 1, cur = 0
                    if(b[i]==1)
                        a[i] = 0;
                    else if(b[i]==0)
                        a[i] = 1;
                }
                else if(prev==1){   // cur = 2, cur = 0
                    if(b[i]==1)
                        a[i] = 1;
                    else if(b[i]==0)
                        a[i] = 0;
                }
                else if(prev==0){       // cur = 1, cur = 2
                    if(b[i]==1)
                        a[i] = 1;
                    else if(b[i]==0)
                        a[i] = 1;
                }
                prev = a[i] + b[i];
            }
            for(int i = 0; i < n; i++){
                p.print(a[i]);
            }
            p.println();
        }
        p.close();
    }

    static long[] sort(long a[]){
        ArrayList<Long> arr = new ArrayList<>();
        for(long i : a){
            arr.add(i);
        }
        Collections.sort(arr);
        for(int i = 0; i < arr.size(); i++){
            a[i] = arr.get(i);
        }
        return a;
    }
    static int[] sort(int a[]){
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i : a){
            arr.add(i);
        }
        Collections.sort(arr);
        for(int i = 0; i < arr.size(); i++){
            a[i] = arr.get(i);
        }
        return a;
    }
    
/* 
*/    
/*
1. Check overflow in pow function or in general
2. Check indices of read array function
3. Think of an easier solution because the problems you solve are always easy
4. Check iterator of loop
5. If still doesn't work, then jump from the 729th floor 'coz "beta tumse na ho paayega"

    Move to top!!
*/
    static class Foster {
        BufferedReader br = new BufferedReader(new InputStreamReader(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 nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        int[] intArray(int n) {                   // Check indices
            int arr[] = new int[n];
            for(int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }
        long[] longArray(int n) {                 // Check indices
            long arr[] = new long[n];
            for(int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
        int[] getBits(int n) {                   //in Reverse Order
            int a[] = new int[31];
            for(int i = 0; i < 31; i++) {
                if(((1<<i) & n) != 0)
                    a[i] = 1;
            }
            return a;
        }
        static String reverse(String s){
            String temp = "";
            for(int i = s.length()-1; i >= 0; i--){
                temp += s.charAt(i);
            }
            return temp;
        }
        static long pow(long... a) {
            long mod = Long.MAX_VALUE;
            if(a.length == 3)   mod = a[2];
            long res = 1;
            while(a[1] > 0) {
                if((a[1] & 1) == 1)
                    res = (res * a[0]) % mod;
                a[1] /= 2;
                a[0] = (a[0] * a[0]) % mod;
            }
            return res;
        }
        static void print(Object... o) {
            for(Object next : o) {
                System.err.print(next + " ");
            }
        }
        static void println(Object... o) {
            for(Object next : o) {
                System.err.print(next + " ");
            }
            System.err.println();
        }
        static void watch(Object...a) throws Exception {
            int i = 1;
            for (Object o: a) {
                boolean found = false;
                if (o.getClass().isArray()) {
                    String type = o.getClass().getName().toString();
                    switch (type) {
                        case "[I": {
                            int[] test = (int[]) o;
                            println(i + " : " + Arrays.toString(test));
                            break;
                        }
                        case "[[I": {
                            int[][] obj = (int[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[J": {
                            long[] obj = (long[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[J": {
                            long[][] obj = (long[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[D": {
                            double[] obj = (double[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[D": {
                            double[][] obj = (double[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[Ljava.lang.String": {
                            String[] obj = (String[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[Ljava.lang.String": {
                            String[][] obj = (String[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[C": {
                            char[] obj = (char[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[C": {
                            char[][] obj = (char[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        default: {
                            println(i + " : type not identified");
                            break;
                        }
                    }
                    found = true;
                }
                if (o.getClass() == ArrayList.class) {
                    println(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == TreeSet.class) {
                    println(i + " : SET = " + o);
                    found = true;
                }
                if (o.getClass() == TreeMap.class) {
                    println(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == HashMap.class) {
                    println(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == LinkedList.class) {
                    println(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == PriorityQueue.class) {
                    println(i + " : PQ = " + o);
                    found = true;
                }
                if (!found) {
                    println(i + " = " + o);
                }
                i++;
            }
        }
    }
}