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.
from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**7)
# sys.stdin = open('inpy.txt', 'r')
# sys.stdout = open('outpy.txt', 'w')
from sys import stdin, stdout
import bisect  # c++ upperbound
import math
import heapq
i_m = 9223372036854775807


def inin():
    return int(input())


def stin():
    return input()


def spin():
    return map(int, stin().split())


def lin():  # takes array as input
    return list(map(int, stin().split()))


def matrix(n):
    #matrix input
    return [list(map(int, input().split()))for i in range(n)]

################################################


def string2intlist(s):
    return list(map(int, s))


def calculate_sum(a, N):  # sum of a to N
    # Number of multiples
    m = N / a
    # sum of first m natural numbers
    sum = m * (m + 1) / 2
    # sum of multiples
    ans = a * sum
    return ans


def series(N):
    return (N*(N+1))//2


def count2Dmatrix(i, list):
    return sum(c.count(i) for c in list)


def modinv(n, p):
    return pow(n, p - 2, p)


def nCr(n, r):
    i = 1
    while i < r:
        n *= (n - i)
        i += 1
    return n // math.factorial(r)


def LCM(x, y):
    return (x * y) // math.gcd(x, y)


def Divisors(n):
    l = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n // i == i):
                l.append(i)
            else:
                l.append(i)
                l.append(n//i)
    return l


def isprime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n % i == 0 or n % (i+2) == 0:
            return False
    return True


prime = []


def SieveOfEratosthenes(n):
    global prime
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    f = []
    for p in range(2, n):
        if prime[p]:
            f.append(p)
    return f


q = []


def dfs(n, d, v, c):
    global q
    v[n] = 1
    x = d[n]
    q.append(n)
    j = c
    for i in x:
        if i not in v:
            f = dfs(i, d, v, c+1)
            j = max(j, f)
            # print(f)
    return j
# d = {}


def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    return K[n][W]


def modularExponentiation(x, n):
    M = 10**9+7
    if(n == 0):
        return 1
    elif (n % 2 == 0):  # n is even
        return modularExponentiation((x*x) % M, n//2)
    else:  # n is odd
        return (x * modularExponentiation((x * x) % M, (n - 1) // 2)) % M


def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if (m == 1):
        return 0

    while (a > 1):

        # q is quotient
        q = a // m

        t = m

        # m is remainder now, process
        # same as Euclid's algo
        m = a % m
        a = t
        t = y

        # Update x and y
        y = x - q * y
        x = t

    # Make x positive
    if (x < 0):
        x = x + m0

    return x


"""*******************************************************"""
for _ in range(inin()):
    n = inin()
    a = stin()

    b = 1 + int(a[0])
    print(1, end='')

    for i in range(1, n):
        if 1 + int(a[i]) != b:
            print(1, end="")
            b = 1 + int(a[i])
        else:
            print(0, end="")
            b = 0 + int(a[i])

    print()
