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 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains the integer $n$ ($1 \leq n \leq 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$.


-----Examples-----

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$.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	b = input()
	ans = ''
	z = 0
	for x in b:
		if int(x) == 0:
			if z != 1:
				ans += '1'
				z = 1
			else:
				ans += '0'
				z = 0
		elif z != 2:
			ans += '1'
			z = 2
		else:
			ans += '0'
			z = 1
	print(ans)


for tc in range(int(input())):
	n = int(input())
	b = input()
	a = ['' for i in range(n)]
	d = ['0' for i in range(n)]
	if b[0] == '0':
		d[0] = '1'
	else:
		d[0] = '2'
	for i in range(1, n):
		if b[i] == '0':
			if d[i - 1] != '1':
				d[i] = '1'
			else:
				d[i] = '0'
		if b[i] == '1':
			if d[i - 1] == '2':
				d[i] = '1'
			else:
				d[i] = '2'
	for i in range(n):
		a[i] = str(eval(d[i] + '-' + b[i]))
	print(''.join(a))


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		l = [1]
		for i in range(1, n):
			v = int(s[i - 1]) + l[i - 1]
			if v == 2:
				l.append((int(s[i]) + 1) % 2)
			elif v == 1:
				l.append(int(s[i]))
			else:
				l.append(1)
		print(''.join(map(str, l)))
except:
	pass


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
for _ in range(int(inp())):
	n = int(inp())
	s = inp()
	prev = 0
	for i in range(n):
		if s[i] == '0':
			if prev != 1:
				print(1, end='')
				prev = 1
			else:
				print(0, end='')
				prev = 0
		elif prev == 2:
			print(0, end='')
			prev = 1
		else:
			print(1, end='')
			prev = 2
	print()


try:
	for i in range(int(input())):
		n = int(input())
		b = list(input())
		a = ['1']
		for i in range(1, n):
			if int(b[i]) + 1 == int(a[i - 1]) + int(b[i - 1]):
				a.append('0')
			else:
				a.append('1')
		a = ''.join(a)
		print(a)
except:
	pass


def solve():
	n = int(input())
	b = input()
	prev = -1
	res = ''
	for curr in b:
		if curr == '0':
			if prev == 1:
				res += '0'
				prev = 0
			else:
				res += '1'
				prev = 1
		elif prev == 2:
			res += '0'
			prev = 1
		else:
			res += '1'
			prev = 2
	print(res)
	return
t = int(input())
for _ in range(t):
	solve()


def maximum_a(value_b: str) -> str:
	value_a = '1'
	for index in range(1, len(value_b)):
		if int(value_a[-1]) + int(value_b[index - 1]) != 1 + int(value_b[index]):
			value_a = value_a + '1'
			continue
		value_a = value_a + '0'
	return value_a

def read_input(filename: str=None) -> None:
	from sys import stdin
	stdin = open(filename) if filename else stdin
	cases = int(stdin.readline())
	while cases:
		cases = cases - 1
		_ = stdin.readline()
		value_b = stdin.readline().strip()
		print(maximum_a(value_b))

def main():
	read_input()
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = '1'
	pre = int(s[0]) + 1
	for i in s[1:]:
		if pre == 0:
			ans += '1'
			pre = int(i) + 1
		elif pre == 1:
			if i == '0':
				ans += '0'
				pre = 0
			else:
				ans += '1'
				pre = 2
		elif i == '1':
			ans += '0'
			pre = 1
		else:
			ans += '1'
			pre = 1
	print(ans)


import sys, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def solve_(srr):
	if len(srr) == 1:
		return '1'
	srr = [int(x) for x in srr]
	cur = [srr[0] + 1]
	res = [1]
	for x in srr[1:]:
		if cur[-1] == 2 and x == 1 or (cur[-1] == 1 and x == 0):
			res.append(0)
			cur.append(x)
		else:
			res.append(1)
			cur.append(x + 1)
	return ''.join((str(x) for x in res))
for case_num in range(int(input())):
	k = int(input())
	srr = input().strip()
	res = solve(srr)
	print(res)


class Solution:

	def solve(self, n, b):
		if n == 1:
			return '1'
		current = int(b[0]) + 1
		result = '1'
		for i in range(1, n):
			s = int(b[i]) + 1
			if s == current:
				s = int(b[i]) + 0
				result += '0'
			else:
				result += '1'
			current = s
		return result
s = Solution()
tests = int(input())
for i in range(tests):
	n = int(input())
	b = input()
	result = s.solve(n, b)
	print(result)


def ass(a, b):
	if a != b:
		print(f'Assertion error:\n{a}\n{b}')

def intline():
	return [int(item) for item in input().split()]

def line():
	return [item for item in input().split()]

def dump(lst):
	for (i, item) in enumerate(lst):
		print(i, item)

def binsearch(arr, a, b):
	m = (a + b) // 2
	if a >= b:
		return a - 1 if arr[a] == 0 else a
	return binsearch(arr, a, m - 1) if arr[m] == 0 else binsearch(arr, m + 1, b)

def f(b):
	arr = [int(ch) for ch in b]
	res = [1 for ch in b]
	for (i, ch) in enumerate(arr):
		if i == 0:
			res[i] = 1 + arr[i]
		else:
			key = [arr[i], res[i - 1]]
			if key == [0, 0]:
				res[i] = 1
			if key == [0, 1]:
				res[i] = 0
			if key == [0, 2]:
				res[i] = 1
			if key == [1, 0]:
				res[i] = 2
			if key == [1, 1]:
				res[i] = 2
			if key == [1, 2]:
				res[i] = 1
	return ''.join([str(res[i] - arr[i]) for (i, ch) in enumerate(res)])
t = intline()[0]
for i in range(t):
	n = intline()[0]
	b = line()[0]
	print(f(b))


def fun():
	for _ in range(int(input())):
		n = int(input())
		b = input().strip()
		c = 0
		a = 0
		l = []
		for i in range(n):
			if b[i] == '0':
				if a == 0:
					l.append('1')
					a += 1
					c = 0
				else:
					l.append('0')
					a = 0
					c = 0
			elif c == 0:
				l.append('1')
				c += 1
				a = 0
			else:
				l.append('0')
				c = 0
				a += 1
		s = ''.join(l)
		print(s)
fun()


t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	a = [1]
	d = int(b[0]) + int(a[0])
	for e in b[1:]:
		if int(e) + 1 == d:
			a.append(0)
			d = int(e)
		else:
			a.append(1)
			d = int(e) + 1
	print(''.join(map(str, a)))


t = int(input())
res = []
for i in range(t):
	n = int(input())
	b = input()
	res.clear()
	res.append('1')
	pa = 1
	if n == 1:
		print('1')
	else:
		for j in range(1, n):
			pb = int(b[j - 1])
			pd = pa + pb
			cb = int(b[j])
			if pd == 2:
				if cb == 0:
					res.append('1')
					pa = 1
				else:
					res.append('0')
					pa = 0
			elif pd == 1:
				if cb == 0:
					res.append('0')
					pa = 0
				else:
					res.append('1')
					pa = 1
			elif pd == 0:
				if cb == 0:
					res.append('1')
					pa = 1
				else:
					res.append('1')
					pa = 1
		print(''.join(res))


def solve(n, b):
	a = '1'
	y = b[0]
	for x in b[1:]:
		if x == y:
			a += '0' if a[-1] == '1' else '1'
		elif x == '1':
			a += '1'
		else:
			a += '0' if a[-1] == '0' else '1'
		y = x
	return a
for _ in range(int(input())):
	n = int(input())
	b = input()
	ans = solve(n, b)
	print(ans)


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in [wtf[i:i + 2] for i in range(1, len(wtf), 2)]:
	n = int(t[0])
	B = t[1]
	A = ['1']
	s = int(A[0]) + int(B[0])
	for (i, b) in enumerate(B):
		if i == 0:
			continue
		elif s == 2:
			if B[i] == '1':
				A.append('0')
			else:
				A.append('1')
			s = 1
		elif s == 1:
			if B[i] == '1':
				A.append('1')
				s = 2
			else:
				A.append('0')
				s = 0
		elif s == 0:
			if B[i] == '0':
				A.append('1')
				s = 1
			else:
				A.append('1')
				s = 2
	print(''.join(A))


z = int(input())
for i in range(z):
	n = int(input())
	s = input()
	ans = ''
	prev = 0
	for j in range(n):
		if s[j] == '0':
			if prev == 1:
				ans = ans + '0'
				prev = 0
			else:
				ans = ans + '1'
				prev = 1
		elif s[j] == '1':
			if prev == 2:
				ans = ans + '0'
				prev = 1
			else:
				ans = ans + '1'
				prev = 2
	print(ans)


q = int(input())
for i in range(q):
	ch1 = False
	ch2 = False
	ans = ''
	n = int(input())
	b = input()
	for j in range(n):
		if b[j] == '0':
			if ch1 == False:
				ch1 = True
				ans += '1'
				ch2 = False
			else:
				ch1 = False
				ans += '0'
				ch2 = False
		elif ch2 == False:
			ch1 = False
			ans += '1'
			ch2 = True
		elif ch1 == False:
			ch1 = True
			ch2 = False
			ans += '0'
	print(ans)


t = int(input())
for tt in range(t):
	n = int(input())
	s = input()
	ss = '1'
	c = 1
	if s[0] == '1':
		c = 2
	for i in range(1, n):
		if c == 2:
			if s[i] == '1':
				ss += '0'
			else:
				ss += '1'
			c = 1
		elif c == 1:
			if s[i] == '1':
				ss += '1'
				c = 2
			else:
				ss += '0'
				c = 0
		elif s[i] == '1':
			ss += '1'
			c = 2
		else:
			ss += '1'
			c = 1
	print(ss)


t = int(input())
for i in range(0, t):
	m = int(input())
	str1 = input()
	str3 = '0'
	str4 = '1'
	if str1[0] == '0':
		bf = 1
		str2 = '1'
	elif str1[0] == '1':
		bf = 2
		str2 = '1'
	for j in range(1, m):
		if str1[j] == '0':
			if bf == 1:
				str2 = str2[0:] + str3[0:]
				bf = 0
			else:
				str2 = str2[0:] + str4[0:]
				bf = 1
		elif bf == 2:
			str2 = str2[0:] + str3[0:]
			bf = 1
		else:
			str2 = str2[0:] + str4[0:]
			bf = 2
	print(str2)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	s = '1'
	prev = int(b[0]) + 1
	for i in range(1, len(b)):
		if prev == 2:
			if b[i] == '1':
				s += '0'
				prev = 1
			else:
				s += '1'
				prev = 1
		elif prev == 1:
			if b[i] == '1':
				s += '1'
				prev = 2
			else:
				s += '0'
				prev = 0
		elif b[i] == '1':
			s += '1'
			prev = 2
		else:
			s += '1'
			prev = 1
	print(s)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	b = list(input())
	a = ['1']
	for i in range(n - 1):
		if int(a[i]) + int(b[i]) == int(b[i + 1]) + 1:
			a.append('0')
		else:
			a.append('1')
	print(''.join(a))


import bisect

def add(arr, x, y):
	x = len(arr) - x
	for i in range(x, len(arr)):
		arr[i] = max(y, arr[i])

def solve(b):
	a = '1'
	for i in range(1, len(b)):
		curr = b[i]
		prev = b[i - 1]
		prev_a = a[i - 1]
		if curr != prev:
			if prev == '1' and prev_a == '0':
				a += '0'
			else:
				a += '1'
		elif prev_a == '1':
			a += '0'
		else:
			a += '1'
	return a
q = int(input())
for _ in range(q):
	n = int(input())
	b = input()
	print(solve(b))


for _ in range(int(input())):
	a = int(input())
	b = input()
	ans = '1'
	for i in range(1, a):
		s = int(ans[-1]) + int(b[i - 1])
		if s == 2:
			ans += str(1 - int(b[i]))
		elif s == 1:
			ans += b[i]
		else:
			ans += '1'
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = input()
	b = ''
	prev = -1
	for i in a:
		if i == '1':
			if prev != 2:
				b += '1'
				prev = 2
			else:
				b += '0'
				prev = 1
		elif prev == 1:
			b += '0'
			prev = 0
		else:
			b += '1'
			prev = 1
	print(b)


t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	temp = list()
	for i in b:
		temp.append(int(i))
	a = list()
	a.append(1)
	for i in range(1, n):
		if a[i - 1] + temp[i - 1] == 2 and temp[i] == 1:
			a.append(0)
		elif a[i - 1] + temp[i - 1] == 2 and temp[i] == 0:
			a.append(1)
		elif a[i - 1] + temp[i - 1] == 1 and temp[i] == 1:
			a.append(1)
		elif a[i - 1] + temp[i - 1] == 1 and temp[i] == 0:
			a.append(0)
		elif a[i - 1] + temp[i - 1] == 0:
			a.append(1)
	for i in a:
		print(i, end='')
	print('\n')


def puzzle(n, b):
	a = '1'
	if b[0] == '1':
		last = '2'
	else:
		last = '1'
	for s in b[1:]:
		if s == '1':
			if last == '0' or last == '1':
				a += '1'
				last = '2'
			else:
				a += '0'
				last = '1'
		elif last == '1':
			a += '0'
			last = '0'
		else:
			a += '1'
			last = '1'
	return a
num_test_cases = int(input())
for i in range(num_test_cases):
	n = int(input())
	b = input()
	print(puzzle(n, b))


t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	a = [1]
	for i in range(1, n):
		if a[i - 1] + int(b[i - 1]) == 2 and b[i] == '1':
			a.append(0)
		elif a[i - 1] + int(b[i - 1]) == 1 and b[i] == '0':
			a.append(0)
		else:
			a.append(1)
	for i in range(n):
		print(a[i], end='')
	print()


import sys
input = sys.stdin.readline

def prog():
	for _ in range(int(input())):
		n = int(input())
		b = input().strip()
		a = []
		lst = -1
		for i in b:
			if int(i) + 1 == lst:
				a.append('0')
				lst = int(i)
			else:
				a.append('1')
				lst = int(i) + 1
		print(''.join(a))
prog()


def solve():
	n = int(input())
	b = input()
	a = ''
	last = '0'
	for digit in b:
		if digit == '0':
			if last == '1':
				last = '0'
				to_add = '0'
			else:
				last = '1'
				to_add = '1'
		elif last == '2':
			last = '1'
			to_add = '0'
		else:
			last = '2'
			to_add = '1'
		a += to_add
	print(a)
t = int(input())
for test in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	c = input()
	b = []
	for i in c:
		b.append(int(i))
	a = [1]
	prev = b[0] + a[0]
	for i in range(1, n):
		if 1 + b[i] == prev:
			a.append(0)
		else:
			a.append(1)
		prev = a[-1] + b[i]
	s = ''
	for i in a:
		s += str(i)
	print(s)


for t in range(int(input())):
	n = int(input())
	a = input()
	b = ['1'] * n
	for i in range(1, n):
		if b[i - 1] == '1':
			if a[i] == '1' and a[i - 1] == '1':
				b[i] = '0'
			elif a[i] == '0' and a[i - 1] == '0':
				b[i] = '0'
		elif a[i] == '0' and a[i - 1] == '1':
			b[i] = '0'
	print(''.join(b))


from sys import stdin, stdout

def II():
	return int(stdin.readline())

def SI():
	return stdin.readline()[:-1]

def solve():
	n = II()
	b = SI()
	p = 0
	for x in b:
		i = int(x)
		if 1 + i != p:
			stdout.write('1')
			p = 1 + i
		else:
			stdout.write('0')
			p = i
	stdout.write('\n')
t = II()
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	b = input()
	a = ['1']
	for i in range(1, n):
		a.append('1')
		if int(a[i - 1]) + int(b[i - 1]) == int(a[i]) + int(b[i]):
			a[i] = '0'
	print(str(''.join((x for x in a))))


t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	ans = []
	previous = 0
	for i in b:
		if i == '0':
			if previous == 1:
				ans.append('0')
				previous = 0
			else:
				ans.append('1')
				previous = 1
		if i == '1':
			if previous == 2:
				ans.append('0')
				previous = 1
			else:
				ans.append('1')
				previous = 2
	print(''.join(ans))


from __future__ import division, print_function
from sys import stdin, stdout
import bisect
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():
	return list(map(int, stin().split()))

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

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

def calculate_sum(a, N):
	m = N / a
	sum = m * (m + 1) / 2
	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)
	return j

def knapSack(W, wt, val, n):
	K = [[0 for x in range(W + 1)] for x in range(n + 1)]
	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:
		return modularExponentiation(x * x % M, n // 2)
	else:
		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 = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	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()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = ''
	j = 1
	ans += '1' * n
	l = list(ans)
	for j in range(1, len(ans)):
		x = int(l[j - 1]) + int(s[j - 1])
		x1 = int(l[j]) + int(s[j])
		if x == x1:
			l[j] = '0'
	final = ''
	for k in range(len(l)):
		final += l[k]
	print(final)


cases = int(input())
for case in range(cases):
	length = int(input())
	b = str(input())
	a = '1'
	last = 0
	if b[0] == '1':
		last = 2
	else:
		last = 1
	for i in range(1, len(b)):
		digit = b[i]
		if last == 2:
			if digit == '0':
				a += '1'
			else:
				a += '0'
			last = 1
		elif last == 1:
			if digit == '0':
				a += '0'
				last = 0
			else:
				a += '1'
				last = 2
		elif digit == '0':
			a += '1'
			last = 1
		else:
			a += '1'
			last = 2
	print(a)


def fun(arr, n):
	out = [0] * n
	out[0] = 1
	prev = int(arr[0]) + out[0]
	for i in range(1, n):
		a = int(arr[i]) + 0
		b = int(arr[i]) + 1
		if prev == b:
			out[i] = 0
			prev = a
		else:
			out[i] = 1
			prev = b
	return out

def joint(arr):
	for elem in arr:
		print(elem, sep='', end='')
for i in range(int(input())):
	n = int(input())
	arr = list(input())
	out = fun(arr, n)
	joint(out)
	print()


t = int(input())
for q in range(t):
	n = int(input())
	b = input()
	a = '1'
	t1 = 0
	for z in range(1, n):
		t1 = int(a[z - 1]) + int(b[z - 1])
		if t1 == 2:
			if b[z] == '1':
				a = a + '0'
			if b[z] == '0':
				a = a + '1'
		if t1 == 1:
			if b[z] == '1':
				a = a + '1'
			if b[z] == '0':
				a = a + '0'
		if t1 == 0:
			a = a + '1'
	print(a)


t = int(input())
for k in range(t):
	n = int(input())
	a = input()
	one = 0
	two = 0
	zero = 0
	ans = ''
	for i in range(len(a)):
		if a[i] == '0':
			if one == 0:
				one += 1
				ans += '1'
				two = 0
				zero = 0
			else:
				ans += '0'
				zero += 1
				two = 0
				one = 0
		elif two == 0:
			two += 1
			ans += '1'
			one = 0
			zero = 0
		else:
			ans += '0'
			one += 1
			two = 0
			zero = 0
	print(ans)


from sys import stdin
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
for _ in range(it()):
	n = it()
	l = list(input())
	s = ['1']
	for i in range(1, n):
		d = int(s[i - 1]) + int(l[i - 1])
		if d == 2:
			s += [str(1 - int(l[i]))]
		elif d == 1:
			s += [l[i]]
		else:
			s += ['1']
	print(''.join(s))


def solve(n, s):
	ans = '1'
	cur = int(s[0]) + 1
	for i in range(1, n):
		if int(s[i]) + 1 == cur:
			ans += '0'
			cur = int(s[i])
		else:
			ans += '1'
			cur = int(s[i]) + 1
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(solve(n, s))


import sys
from collections import deque
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input())
il = lambda : list(map(int, input().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
for _ in range(int(input())):
	n = int(input())
	b = input()
	d = [1 + int(b[0])]
	a = ['1']
	for i in range(1, n):
		if d[i - 1] != 1 + int(b[i]):
			d.append(1 + int(b[i]))
			a.append('1')
		else:
			d.append(int(b[i]))
			a.append('0')
	print(''.join(a))


import sys
import math
from collections import defaultdict, deque
input = sys.stdin.readline

def inar():
	return [int(el) for el in input().split()]

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		st = input().strip()
		ans = -1
		result = []
		for i in range(n):
			if i == 0:
				result.append(1)
				ans = int(st[i]) + 1
				continue
			if ans == 2:
				if st[i] == '1':
					result.append(0)
				else:
					result.append(1)
				ans = 1
			else:
				if ans == 1:
					if st[i] == '1':
						result.append(1)
					else:
						result.append(0)
				else:
					result.append(1)
				ans = int(st[i]) + result[-1]
		print(''.join(map(str, result)))
main()


t = int(input())
answer = []
for _ in range(t):
	n = int(input())
	b = input()
	a = '1'
	if b[0] == '1':
		ans = '2'
	else:
		ans = '1'
	for i in range(1, n):
		if b[i] == '0':
			if ans[-1] == '0' or ans[-1] == '2':
				a += '1'
				ans += '1'
			elif ans[-1] == '1':
				a += '0'
				ans += '0'
		if b[i] == '1':
			if ans[-1] == '1':
				a += '1'
				ans += '2'
			elif ans[-1] == '0':
				a += '1'
				ans += '2'
			elif ans[-1] == '2':
				a += '0'
				ans += '1'
	answer.append(a)
print('\n'.join(map(str, answer)))


import sys

def input():
	return sys.stdin.readline().rstrip('\n')
test_case = int(input())
for _ in range(test_case):
	n = int(input())
	b = input()
	a = ['1'] * n
	ans = [''] * n
	for i in range(n):
		ans[i] = str(int(b[i]) + int(a[i]))
	for i in range(1, n):
		if ans[i] == ans[i - 1]:
			a[i] = str(int(a[i]) - 1)
			ans[i] = str(int(ans[i]) - 1)
	print(''.join(a))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	b = []
	for c in input():
		b.append(c)
	b[0] = chr(ord(b[0]) + 1)
	print(1, end='')
	for i in range(1, len(b)):
		if chr(ord(b[i]) + 1) != b[i - 1]:
			b[i] = chr(ord(b[i]) + 1)
			print(1, end='')
		else:
			print(0, end='')
	print()


def solve():
	n = int(input())
	s = input()
	a = ''
	c = ''
	for i in range(0, n):
		if i == 0:
			a += '1'
			if s[i] == '1':
				c += '2'
			else:
				c += '1'
		elif c[i - 1] == '2':
			if s[i] == '1':
				a += '0'
				c += '1'
			else:
				a += '1'
				c += '1'
		elif c[i - 1] == '1':
			if s[i] == '1':
				a += '1'
				c += '2'
			else:
				a += '0'
				c += '0'
		elif c[i - 1] == '0':
			if s[i] == '1':
				a += '1'
				c += '2'
			else:
				a += '1'
				c += '1'
	return a
T = int(input())
for i in range(T):
	print(solve())


for nt in range(int(input())):
	n = int(input())
	a = input()
	prev = -1
	ans = ''
	for i in a:
		if i == '1':
			if prev != 2:
				ans += '1'
				prev = 2
			else:
				ans += '0'
				prev = 1
		elif prev != 1:
			ans += '1'
			prev = 1
		else:
			ans += '0'
			prev = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = '1'
	p = s[0]
	for i in s[1:]:
		if i == '1':
			if t[-1] == '1' and p == '1':
				t += '0'
			else:
				t += '1'
		elif t[-1] == '1' and p == '0' or (t[-1] == '0' and p == '1'):
			t += '0'
		else:
			t += '1'
		p = i
	print(t)


for s in [*open(0)][2::2]:
	r = ''
	p = 0
	for x in map(int, s[:-1]):
		p = x + (x + 1 != p)
		r += str(p - x)
	print(r)


def solve():
	n = int(input())
	b = input()
	(a, p) = ('', '?')
	for c in b:
		(x, d) = ('1', '2' if c == '1' else '1')
		if d == p:
			(x, d) = ('0', c)
		a += x
		p = d
	print(a)
t = int(input())
for _ in range(t):
	solve()


import sys, io, os, math
from math import ceil, log, gcd
from itertools import permutations
mod = 1000000007
mod1 = 998244353

def printlist(n):
	sys.stdout.write(' '.join(map(str, n)) + '\n')

def printf(n):
	sys.stdout.write(str(n) + '\n')

def printns(n):
	sys.stdout.write(str(n))

def intinp():
	return int(sys.stdin.readline())

def strinp():
	return sys.stdin.readline()

def arrinp():
	return list(map(int, sys.stdin.readline().strip().split()))

def mulinp():
	return map(int, sys.stdin.readline().strip().split())

def flush():
	return stdout.flush()

def power_two(x):
	return 1 << x

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	n = intinp()
	b = strinp()
	a = '1'
	for i in range(1, n):
		if 1 + int(b[i]) != int(a[i - 1]) + int(b[i - 1]):
			a += '1'
		else:
			a += '0'
	print(a)

def main():
	tc = intinp()
	while tc:
		solve()
		tc -= 1
main()


def solve():
	s = int(input())
	a = input()
	ret = '1'
	for i in range(1, len(a)):
		if a[i] == '0':
			if a[i - 1] == '1':
				if ret[-1] == '1':
					ret += '1'
				else:
					ret += '0'
			elif ret[-1] == '0':
				ret += '1'
			else:
				ret += '0'
		elif a[i - 1] == '1':
			if ret[-1] == '1':
				ret += '0'
			else:
				ret += '1'
		elif ret[-1] == '0':
			ret += '1'
		else:
			ret += '1'
	return ret
for i in range(int(input())):
	print(solve())


def solve(n, b):
	last = int(b[0]) + 1
	res = '1'
	for i in range(1, n):
		x = int(b[i])
		if x == 0:
			if last == 1:
				res += '0'
				last = 0
			else:
				res += '1'
				last = 1
		elif last == 2:
			res += '0'
			last = 1
		else:
			res += '1'
			last = 2
	return res
for _ in range(int(input())):
	n = int(input())
	b = input()
	print(solve(n, b))


def main():
	T = int(input())
	for i in range(T):
		n = input()
		n = int(n)
		s2 = input()
		ans = ['0' for i in range(n)]
		ans[0] = '1'
		prev_sum = 1 + ord(s2[0]) - ord('0')
		for i in range(1, n):
			delta = prev_sum - ord(s2[i]) + ord('0')
			if delta == 1:
				ans[i] = '0'
			else:
				ans[i] = '1'
			prev_sum = ord(ans[i]) + ord(s2[i]) - 2 * ord('0')
		print(''.join(ans))
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for i in range(t):
	n = int(input())
	no = input()
	a = []
	end = 0
	for i in range(len(no)):
		case1 = int(no[i]) + 1
		case2 = int(no[i]) + 0
		if end == 0:
			a.append(max(case1, case2))
			end += 1
		elif a[end - 1] != case1 and a[end - 1] != case2:
			a.append(max(case1, case2))
			end += 1
		elif a[end - 1] != case1:
			a.append(case1)
			end += 1
		else:
			a.append(case2)
			end += 1
	for i in range(len(no)):
		print(a[i] - int(no[i]), end='')
	print('')


for _ in range(int(input())):
	n = int(input())
	b = input()
	(a, res) = ('', '')
	for num in b:
		if num == '0':
			if res == '':
				a += '1'
				res += '1'
			elif res[-1] == '1':
				res += '0'
				a += '0'
			else:
				res += '1'
				a += '1'
		elif res == '':
			res += '2'
			a += '1'
		elif res[-1] == '2':
			res += '1'
			a += '0'
		elif res[-1] == '1':
			res += '2'
			a += '1'
		else:
			res += '2'
			a += '1'
	print(a)


from sys import stdin, stdout
t = int(stdin.readline())
while t:
	t -= 1
	n = int(input())
	b = input()
	prev = -1
	ans = []
	for i in b:
		if i == '1':
			if prev == 2:
				ans.append(0)
				prev = 1
			else:
				ans.append(1)
				prev = 2
		elif prev == 1:
			ans.append(0)
			prev = 0
		else:
			ans.append(1)
			prev = 1
	for j in ans:
		print(j, end='')
	print()


t = input()
t = int(t)
for i in range(t):
	n = input()
	n = int(n)
	b = input()
	a = ''
	for j in range(n):
		if j == 0:
			a += '1'
		else:
			test = int(b[j]) + 1
			if test == k:
				a += '0'
			else:
				a += '1'
		k = int(a[j]) + int(b[j])
	print(a)


from sys import stdin, stdout

def gmi():
	return map(int, stdin.readline().strip().split())

def gms():
	return map(str, stdin.readline().strip().split())

def gari():
	return list(map(int, stdin.readline().strip().split()))

def gars():
	return list(map(int, stdin.readline().strip().split()))

def gs():
	return stdin.readline().strip()

def gls():
	return list(stdin.readline())

def gi():
	return int(stdin.readline())
t = gi()
while t:
	t -= 1
	n = gi()
	s = gs()
	ans = ''
	p = ''
	if s[0] == '1':
		ans += '1'
		p = '2'
	else:
		ans += '1'
		p = '1'
	for i in s[1:]:
		if i == '0':
			if p == '1':
				ans += '0'
				p = '0'
			else:
				ans += '1'
				p = '1'
		elif p == '2':
			ans += '0'
			p = '1'
		else:
			ans += '1'
			p = '2'
	print(ans)


import sys
lines = sys.stdin.readlines()
cur_line = -1

def input():
	global lines, cur_line
	cur_line += 1
	return lines[cur_line][:-1]
for _ in range(int(input())):
	n = int(input())
	b = input()
	a = [1]
	for (i, v) in enumerate(b[1:]):
		if int(v) + 1 == int(b[i]) + a[-1]:
			a.append(0)
		else:
			a.append(1)
	print(''.join((str(i) for i in a)))


for _ in range(int(input())):
	n = int(input())
	b = input()
	a = '1'
	if b[0] == '1':
		s = 2
	else:
		s = 1
	for i in range(1, n):
		if s == 2:
			if b[i] == '1':
				a += '0'
			else:
				a += '1'
			s = 1
		elif s == 0:
			a += '1'
			if b[i] == '1':
				s = 2
			else:
				s = 1
		else:
			a += b[i]
			if b[i] == '1':
				s = 2
			else:
				s = 0
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	res = '1'
	s = str(int(res[0]) + int(b[0]))
	for i in range(1, len(b)):
		if s[i - 1] == '0':
			if b[i] == '0':
				res += '1'
			elif b[i] == '1':
				res += '1'
		elif s[i - 1] == '1':
			if b[i] == '0':
				res += '0'
			elif b[i] == '1':
				res += '1'
		elif s[i - 1] == '2':
			if b[i] == '0':
				res += '1'
			elif b[i] == '1':
				res += '0'
		s += str(int(res[i]) + int(b[i]))
	print(res)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	n = inp()
	s = insr()
	last = -1
	for ch in s:
		if ch == '0':
			if last == 1:
				print('0', end='')
				last = 0
			else:
				print('1', end='')
				last = 1
		elif last == 2:
			print('0', end='')
			last = 1
		else:
			print('1', end='')
			last = 2
	print()


import sys
from collections import defaultdict as dd
from collections import Counter as cc
from queue import Queue
import math
import itertools
import functools
from operator import ixor
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	q = int(input())
	w = input()
	a = [1]
	d = 0
	s = 0
	for i in range(1, q):
		if w[i] == w[i - 1]:
			a.append(1 - a[-1])
		elif w[i] == '0':
			if a[i - 1] == 1:
				a.append(1)
			else:
				a.append(0)
		else:
			a.append(1)
	print(''.join(list(map(str, a))))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = ''
	for i in range(n):
		if i == 0:
			ans += '1'
		elif s[i] == s[i - 1]:
			if ans[-1] == '0':
				ans += '1'
			else:
				ans += '0'
		elif s[i] == '0' and ans[-1] == '0':
			ans += '0'
		else:
			ans += '1'
	print(ans)


t = int(input())
for _ in range(0, t):
	n = int(input())
	b = list(input())
	b = [int(i) for i in b]
	a = [0 for i in b]
	a[0] = 1
	for i in range(1, n):
		if b[i] + 1 != a[i - 1] + b[i - 1]:
			a[i] = 1
	for i in a:
		print(i, end='')
	print('')


def brate(b):
	a = '1'
	i = 1
	while i < len(b):
		k = int(b[i:i + 1:1])
		k1 = int(a[i - 1:i:1])
		k2 = int(b[i - 1:i:1])
		if k1 + k2 == 2:
			if k == 1:
				a += '0'
			else:
				a += '1'
		elif k1 + k2 == 1:
			if k == 1:
				a += '1'
			else:
				a += '0'
		else:
			a += '1'
		i += 1
	return a
n = int(input())
while n > 0:
	j = input()
	k = str(input())
	print(brate(k))
	n -= 1


t = int(input())
while t > 0:
	t -= 1
	k = int(input())
	n = input()
	res = []
	cur = 0
	for i in n:
		i = int(i)
		if cur == 2:
			if i == 0:
				res.append('1')
				cur = 1
			elif i == 1:
				res.append('0')
				cur = 1
		elif cur == 1:
			if i == 1:
				res.append('1')
				cur = 2
			if i == 0:
				res.append('0')
				cur = 0
		elif i == 1:
			res.append('1')
			cur = 2
		else:
			res.append('1')
			cur = 1
	print(''.join(res))


t = int(input())
answers = []
for i in range(t):
	n = int(input())
	b = input()
	num = '1'
	a = '1'
	for j in range(1, n):
		if b[j] == b[j - 1]:
			if num == '1':
				num = '0'
			else:
				num = '1'
		elif b[j] == '1':
			num = '1'
		a = a + num
	answers.append(a)
for answer in answers:
	print(answer)


for _ in range(int(input())):
	n = input()
	a = input()
	b = ''
	flag = 0
	for i in a:
		if i == '1' and flag == 2:
			b += '0'
			flag = 1
			continue
		if i == '1' and (flag == 1 or flag == 0):
			b += '1'
			flag = 2
			continue
		if i == '0' and flag == 1:
			b += '0'
			flag = 0
			continue
		if i == '0' and (flag == 2 or flag == 0):
			b += '1'
			flag = 1
	print(b)


caseNum = int(input())
rels = []

def getResult(str, length):
	pre = '2'
	ls = []
	for ele in str:
		if pre == '2':
			pre = ele
			ls.append('1')
			continue
		if ele == pre:
			if ls[-1] == '0':
				ls.append('1')
			else:
				ls.append('0')
		elif ele == '0':
			ls.append(ls[-1])
		else:
			ls.append('1')
		pre = ele
	return ''.join(ls)
for i in range(caseNum):
	length = int(input())
	str = input()
	rels.append(getResult(str, length))
for ele in rels:
	print(ele)


import math
import os
import random
import re
import sys

def find_mystery_binary(b, sz):
	a = [1] * sz
	last = 0
	for i in range(sz):
		if last == int(a[i]) + int(b[i]):
			a[i] = str(int(a[i]) - 1)
		last = int(a[i]) + int(b[i])
	str_a = [str(ele) for ele in a]
	print(''.join(str_a))
n = int(input())
for i in range(n):
	sz = int(input())
	b = input()
	find_mystery_binary(b, sz)


def solve(n, b):
	a = [1] * n
	d = [0] * n
	d[0] = a[0] + b[0]
	for i in range(1, n):
		if b[i] + 1 != d[i - 1]:
			a[i] = 1
			d[i] = b[i] + a[i]
		else:
			a[i] = 0
			d[i] = b[i] + a[i]
	return ''.join(map(str, a))
t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input()))
	print(solve(n, b))


for _ in ' ' * int(input()):
	n = int(input())
	s = list(input())
	ans = [0] * n
	a = [0] * n
	a[0] = '1'
	ans[0] = str(int(a[0]) + int(s[0]))
	for i in range(1, n):
		if s[i] == '1':
			if not ans[i - 1] == '2':
				a[i] = '1'
				ans[i] = '2'
			else:
				a[i] = '0'
				ans[i] = '1'
		elif not ans[i - 1] == '1':
			a[i] = '1'
			ans[i] = '1'
		else:
			a[i] = '0'
			ans[i] = '0'
	print(''.join(a))


for _ in range(int(input())):
	n = int(input())
	b = input()
	a = '1'
	for i in range(1, n):
		if int(b[i]) + 1 != int(a[i - 1]) + int(b[i - 1]):
			a += '1'
		else:
			a += '0'
	print(a)


def solve():
	n = int(input())
	b = input()
	f = 0
	r = 0
	a = ''
	for i in b:
		if i == '1':
			if f == 0:
				a = a + '1'
				f = 2
			elif f == 1:
				a = a + '1'
				f = 2
			elif f == 2:
				a = a + '0'
				f = 1
		elif f == 0:
			a = a + '1'
			f = 1
		elif f == 1:
			a = a + '0'
			f = 0
		elif f == 2:
			a = a + '1'
			f = 1
	print(a)
for testis in range(int(input())):
	solve()


def answer():
	a = ''
	(f2, f1) = (False, False)
	for i in b:
		if i == '1':
			if not f2:
				a += '1'
				(f2, f1) = (True, False)
			else:
				a += '0'
				(f2, f1) = (False, True)
		else:
			if not f1:
				a += '1'
				f1 = True
			else:
				a += '0'
				f1 = False
			f2 = False
	return a
for T in range(int(input())):
	n = int(input())
	b = input()
	print(answer())


def opta(b, n):
	a = ''
	for i in range(n):
		if i == 0:
			a += '1'
		elif int(a[i - 1]) + int(b[i - 1]) == int(b[i]) + 1:
			a += '0'
		else:
			a += '1'
	return a
for _ in range(int(input())):
	n = int(input())
	b = input()
	print(opta(b, n))


t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	if b[0] == '1':
		a = '1'
	elif b[0] == '0':
		a = '1'
	s = str(int(a[0]) + int(b[0]))
	for j in range(1, n):
		if 1 + int(b[j]) != int(s[j - 1]):
			a = a + '1'
			s = s + str(1 + int(b[j]))
		else:
			a = a + '0'
			s = s + str(0 + int(b[j]))
	print(a)


from sys import stdin, exit
from bisect import bisect_left as bl, bisect_right as br
from itertools import accumulate
input = lambda : stdin.readline()[:-1]
intput = lambda : int(input())
sinput = lambda : input().split()
intsput = lambda : map(int, sinput())

def dprint(*args, **kwargs):
	if debugging:
		print(*args, **kwargs)
debugging = 1
t = intput()
for _ in range(t):
	n = intput()
	b = list(map(int, input()))
	a = [2 - b[0]]
	if a[0] == 2:
		a[0] -= 1
	for i in range(1, n):
		prev = a[i - 1] + b[i - 1]
		if prev == 2:
			target = 1
		elif b[i] == 1:
			target = 2
		elif prev == 1:
			target = 0
		else:
			target = 1
		a.append(target - b[i])
	print(''.join(map(str, a)))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	sa = ''
	prev = -1
	for i in range(n):
		param = s[i]
		if prev == 2:
			if param == '1':
				sa += '0'
			else:
				sa += '1'
			prev = 1
		elif prev == 1:
			if param == '1':
				sa += '1'
				prev = 2
			else:
				sa += '0'
				prev = 0
		else:
			sa += '1'
			prev = int(param) + 1
	print(sa)


t = int(input())
for test in range(t):
	lenth = int(input())
	binary = input()
	ansString = ''
	latest = -1
	for ele in binary:
		if 1 + int(ele) != latest:
			ansString += '1'
			latest = 1 + int(ele)
		else:
			ansString += '0'
			latest = 0 + int(ele)
	print(ansString)


test_cases = int(input())
res = []
for test in range(test_cases):
	n = int(input())
	st = input()
	rst = '1'
	p = 0
	if st[0] == '1':
		p = 2
	else:
		p = 1
	for i in range(1, n):
		if p == 0:
			rst += '1'
			if st[i] == '1':
				p = 2
			else:
				p = 1
		elif p == 1:
			if st[i] == '1':
				rst += '1'
				p = 2
			else:
				rst += '0'
				p = 0
		elif st[i] == '1':
			rst += '0'
			p = 1
		else:
			rst += '1'
			p = 1
	res.append(rst)
for value in res:
	print(value)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = input().rstrip()
	res = ['1']
	last = -1
	if a[0] == '1':
		last = 2
	else:
		last = 1
	for i in range(1, n):
		if last == 2:
			last = 1
			if a[i] == '1':
				res.append('0')
			else:
				res.append('1')
		elif last == 1:
			if a[i] == '1':
				res.append('1')
				last = 2
			else:
				res.append('0')
				last = 0
		else:
			res.append('1')
			if a[i] == '1':
				last = 2
			else:
				last = 1
	print(''.join(res))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = []
	d = []
	c = 0
	i = 0
	for i in range(n):
		if i == 0:
			if s[i] == '0':
				d.append('1')
			else:
				d.append('2')
			ans.append('1')
		elif s[i] == '0':
			if d[i - 1] == '2':
				ans.append('1')
				d.append('1')
			elif d[i - 1] == '1':
				ans.append('0')
				d.append('0')
			else:
				ans.append('1')
				d.append('1')
		elif s[i] == '1':
			if d[i - 1] == '2':
				ans.append('0')
				d.append('1')
			elif d[i - 1] == '1':
				ans.append('1')
				d.append('2')
			else:
				ans.append('1')
				d.append('2')
	x = ''
	print(''.join(ans))


for _ in range(0, int(input())):
	n = int(input())
	s = input()
	p = -1
	a = ''
	for x in s:
		if x == '0':
			if p != 1:
				a += '1'
				p = 1
			else:
				a += '0'
				p = 0
		elif p == 2:
			a += '0'
			p = 1
		else:
			a += '1'
			p = 2
	print(a)


import sys
input = sys.stdin.readline
ins = lambda : input().rstrip()
ini = lambda : int(input().rstrip())
inm = lambda : map(int, input().rstrip().split())
inl = lambda : list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))
t = ini()
for _ in range(t):
	n = ini()
	b = ins()
	ans = ''
	prev = -1
	for i in b:
		if i == '1':
			if prev != 2:
				ans += '1'
				prev = 2
			else:
				ans += '0'
				prev = 1
		elif prev != 1:
			ans += '1'
			prev = 1
		else:
			ans += '0'
			prev = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = input()
	a = '1'
	for i in range(1, n):
		if a[i - 1] + b[i - 1] == '11':
			if b[i] == '1':
				a += '0'
			else:
				a += '1'
		elif a[i - 1] + b[i - 1] == '10' or a[i - 1] + b[i - 1] == '01':
			if b[i] == '1':
				a += '1'
			else:
				a += '0'
		else:
			a += '1'
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	a = '1'
	r = '1'
	for j in range(n):
		if b[j:j + 2] == '00' and a[j] == '1' or (b[j:j + 2] == '11' and a[j] == '1'):
			a += '0'
		elif b[j:j + 2] == '10' and a[j] == '1' or (b[j:j + 2] == '01' and a[j] == '1'):
			a += '1'
		elif b[j:j + 2] == '01' and a[j] == '0':
			a += '1'
		elif b[j:j + 2] == '10' and a[j] == '0':
			a += '0'
		elif b[j:j + 2] == '00' and a[j] == '0' or (b[j:j + 2] == '11' and a[j] == '0'):
			a += '1'
	print(a)


t = int(input())
anss = []
while t:
	t -= 1
	n = int(input())
	b = input()
	ans = '1'
	mae = 1 + int(b[0])
	for i in b[1:]:
		if mae == 2:
			if i == '0':
				ans += '1'
			else:
				ans += '0'
			mae = 1
		elif mae == 1:
			if i == '0':
				ans += '0'
				mae = 0
			else:
				ans += '1'
				mae = 2
		else:
			ans += '1'
			mae = 1 + int(i)
	anss.append(ans)
print(*anss, sep='\n')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	pr = 0
	for i in range(n):
		if int(s[i]) + 1 != pr:
			print(1, end='')
			pr = int(s[i]) + 1
		else:
			print(0, end='')
			pr = int(s[i])
	print()


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	b = input()
	for i in range(n):
		if i == 0:
			a = '1'
			l = int(a) + int(b[0])
		elif int(b[i]) + 1 == l:
			a = ''.join([a, '0'])
			l = 0 + int(b[i])
		else:
			a = ''.join([a, '1'])
			l = 1 + int(b[i])
	print(a)


for iter in range(int(input())):
	(_, s) = (input(), input())
	cur_sum = -1
	for elem in s:
		if int(elem) + 1 == cur_sum:
			print(0, end='')
			cur_sum = int(elem)
		else:
			print(1, end='')
			cur_sum = int(elem) + 1
	print()


import sys
import math
import bisect
import functools
from functools import lru_cache
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from heapq import heappush, heappop, heapify
from collections import defaultdict as dd
from collections import Counter as cc
from bisect import bisect_left as bl
from bisect import bisect_right as br

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
sys.setrecursionlimit(100000000)
intinp = lambda : int(input().strip())
stripinp = lambda : input().strip()
fltarr = lambda : list(map(float, input().strip().split()))
intarr = lambda : list(map(int, input().strip().split()))
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
MOD = 1000000007
num_cases = intinp()
for _ in range(num_cases):
	n = intinp()
	b = stripinp()
	ans = ''
	prev = 5
	for val in b:
		if val == '1':
			if prev != 2:
				ans += '1'
				prev = 2
			else:
				ans += '0'
				prev = 1
		elif prev != 1:
			ans += '1'
			prev = 1
		else:
			ans += '0'
			prev = 0
	print(ans)


import sys
import os.path
from collections import *
import math
import bisect
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	b = input().rstrip('\n')
	d = ''
	i = 0
	while i < n:
		if i == 0:
			if b[i] == '0':
				d = '1'
				print(1, end='')
			else:
				d = '2'
				print(1, end='')
		elif d == '2':
			d = '1'
			print(1 - int(b[i]), end='')
		elif d == '1' and b[i] == '1':
			d = '2'
			print(1, end='')
		elif d == '1' and b[i] == '0':
			d = '0'
			print(0, end='')
		elif d == '0' and b[i] == '1':
			d = '2'
			print(1, end='')
		elif d == '0' and b[i] == '0':
			d = '1'
			print(1, end='')
		i += 1
	print()


for i in range(int(input())):
	n = int(input())
	x = list(map(int, list(input())))
	s = ''
	a = -2
	for i in range(n):
		if x[i] + 1 == a:
			s += '0'
			a = x[i]
		else:
			s += '1'
			a = x[i] + 1
	print(s)


import sys
input = sys.stdin.readline

def solution(n, b):
	b = [int(char) for char in b[0:-1]]
	a = ['1']
	d = [b[0] + 1]
	for i in range(1, n):
		if 1 + b[i] != d[-1]:
			a.append('1')
			d.append(1 + b[i])
		else:
			a.append('0')
			d.append(0 + b[i])
	a = ''.join(a)
	print(a)
T = int(input())
for t in range(T):
	n = int(input())
	b = input()
	solution(n, b)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	prev = int(s[0])
	l.append(prev + 1)
	ans = ['1']
	for i in range(1, n):
		if s[i] == '1':
			if l[-1] == 2:
				l.append(1)
				ans.append('0')
			elif l[-1] == 1:
				l.append(2)
				ans.append('1')
			else:
				l.append(2)
				ans.append('1')
		elif l[-1] == 2:
			l.append(1)
			ans.append('1')
		elif l[-1] == 1:
			l.append(0)
			ans.append('0')
		else:
			l.append(1)
			ans.append('1')
	print(''.join(ans))


for _ in range(int(input())):
	n = int(input())
	b = input()
	ans = '1'
	prea = '1'
	preb = b[0:1]
	for i in b[1:]:
		if i == '1':
			if prea == '1' and preb == '1':
				ans = ans + '0'
				prea = '0'
				preb = '1'
			else:
				ans = ans + '1'
				prea = '1'
				preb = '1'
		elif prea == '0' and preb == '0':
			ans = ans + '1'
			prea = '1'
			preb = '0'
		elif prea == '1' and preb == '1':
			ans = ans + '1'
			prea = '1'
			preb = '0'
		else:
			ans = ans + '0'
			prea = '0'
			preb = '0'
	print(ans)


for t in range(int(input())):
	n = int(input())
	b = input()
	a = ''
	o1 = False
	n0 = True
	frst = True
	for i in b:
		if i == '0':
			if frst or n0:
				frst = False
				o1 = False
				n0 = False
				a += '1'
			elif o1:
				o1 = False
				n0 = False
				a += '1'
			else:
				a += '0'
				o1 = False
				n0 = True
		else:
			if frst or n0:
				frst = False
				o1 = True
				a += '1'
			elif not o1:
				o1 = True
				a += '1'
			else:
				a += '0'
				o1 = False
			n0 = False
	print(a)


n = int(input())
for _ in range(n):
	m = int(input())
	s = input()
	ans = []
	ans.append('1')
	for i in range(1, m):
		if s[i] == s[i - 1]:
			if ans[-1] == '1':
				ans.append('0')
			else:
				ans.append('1')
		elif s[i - 1] == '1' and ans[-1] == '0':
			ans.append('0')
		else:
			ans.append('1')
	print(''.join(ans))


for i in range(int(input())):
	n = int(input())
	x = input()
	b = []
	for i in range(n):
		b.append(int(x[i]))
	a = [1]
	for i in range(1, n):
		if b[i - 1] + a[-1] == 2:
			if b[i] == 1:
				a.append(0)
			else:
				a.append(1)
		elif b[i - 1] + a[-1] == 1:
			if b[i] == 1:
				a.append(1)
			else:
				a.append(0)
		else:
			a.append(1)
	for i in a:
		print(i, end='')
	print()


from collections import *
from math import *
for y in range(int(input())):
	n = int(input())
	s = input()
	ans = ''
	prev = 0
	for i in range(n):
		if prev == 0:
			if s[i] == '0':
				ans += '1'
				prev = 1
			else:
				ans += '1'
				prev = 2
		elif prev == 1:
			if s[i] == '0':
				ans += '0'
				prev = 0
			else:
				ans += '1'
				prev = 2
		elif s[i] == '0':
			ans += '1'
			prev = 1
		else:
			ans += '0'
			prev = 1
	print(ans)


from collections import defaultdict, deque
import sys
import bisect
import math
input = sys.stdin.readline
mod = 1000000007
t = int(input())
for ii in range(t):
	n = int(input())
	b = [int(i) for i in input() if i != '\n']
	ans = [1]
	first = [1 + b[0]]
	for i in range(1, n):
		if b[i] + 1 == first[-1]:
			ans.append(0)
		else:
			ans.append(1)
		first.append(b[i] + ans[-1])
	ans = ''.join(map(str, ans))
	print(ans)


def main():
	for _ in range(int(input())):
		n = int(input())
		b = input()
		a = ''
		pre = -1
		d = ''
		for i in b:
			if pre == -1:
				if i == '1':
					pre = '2'
					a += '1'
				else:
					pre = '1'
					a += '1'
			elif i == '0':
				if pre != '1':
					pre = '1'
					a += '1'
				else:
					pre = '0'
					a += '0'
			elif pre == '0':
				pre = '2'
				a += '1'
			elif pre == '1':
				pre = '2'
				a += '1'
			else:
				pre = '1'
				a += '0'
		print(a)
main()


for _ in range(int(input())):
	n = int(input())
	b = input()
	flag = False
	a = '1'
	j = b[0]
	for i in b[1:]:
		if j == i:
			k = a[-1]
			if k == '1':
				a += '0'
			else:
				a += '1'
		elif i == '1':
			a += '1'
		else:
			a += a[-1]
		j = i
	print(a)


for u in range(int(input())):
	n = int(input())
	d = input()
	b = [int(i) for i in d]
	ans = ['1']
	t = b[0] + 1
	if n != 1:
		for i in range(1, len(b)):
			if b[i] + 1 != t:
				ans.append('1')
				t = b[i] + 1
			else:
				ans.append('0')
				t = b[i]
	print(''.join(ans))


t = int(input())
while t > 0:
	n = int(input())
	b = input()
	b_n = list(b)
	a = ['1']
	for i in range(n - 1):
		if int(a[i]) + int(b_n[i]) == 2:
			if int(b_n[i + 1]) == 1:
				a.append('0')
			else:
				a.append('1')
		elif int(a[i]) + int(b_n[i]) == 1:
			a.append(b_n[i + 1])
		else:
			a.append('1')
	str1 = ''
	str2 = str1.join(a)
	print(str2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = [int(s[0]) + 1]
	for (i, j) in enumerate(s[1:]):
		if int(j) + 1 != res[i]:
			res.append(int(j) + 1)
		else:
			res.append(int(j))
	print(''.join((str(i - int(j)) for (i, j) in zip(res, s))))


t = int(input())
for _ in range(t):
	n = int(input())
	b = str(input())
	s = ''
	a = '1'
	print(a, end='')
	if b[0] == '0':
		s = 1
	else:
		s = 2
	for i in range(1, n):
		if s == 2:
			if b[i] == '1':
				a = '0'
			else:
				a = '1'
		if s == 1:
			if b[i] == '1':
				a = '1'
			else:
				a = '0'
		if s == 0:
			a = '1'
		s = int(a) + int(b[i])
		print(a, end='')
	print()


import sys

def solve():
	n = int(input())
	b = input()
	s = ['1'] * n
	for i in range(1, n):
		if int(s[i]) + int(b[i]) == int(s[i - 1]) + int(b[i - 1]):
			s[i] = '0'
	return ''.join(s)
t = int(input())
for i in range(t):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	ans = []
	for i in range(n):
		if b[i] == '0':
			if i == 0:
				ans.append('1')
			elif ans[-1] == '1' and b[i - 1] == '0' or (ans[-1] == '0' and b[i - 1] == '1'):
				ans.append('0')
			else:
				ans.append('1')
		elif i == 0:
			ans.append('1')
		elif b[i - 1] == '1' and ans[-1] == '1':
			ans.append('0')
		else:
			ans.append('1')
	for i in range(n):
		print(ans[i], end='')
	print('\n')


for _ in range(int(input())):
	n = int(input())
	b = input()
	ch = '1'
	a = [ch]
	for i in range(1, len(b)):
		if b[i - 1] == b[i]:
			ch = ['0', '1'][ch == '0']
		elif b[i - 1] == '0':
			ch = '1'
		a.append(ch)
	print(''.join(a))


def main():
	from sys import stdin, stdout
	print = stdout.write
	input = stdin.readline
	t = int(input())
	for i in range(t):
		n = int(input())
		b = input()[:-1]
		a = '1'
		last_digit_sum = 1 + int(b[0])
		for digit_index in range(1, len(b)):
			current_digit = int(b[digit_index])
			if last_digit_sum == 2:
				a += f'{(0 if current_digit else 1)}'
				last_digit_sum = 1
			elif last_digit_sum == 1:
				a += f'{(1 if current_digit else 0)}'
				last_digit_sum = 2 if current_digit else 0
			else:
				a += '1'
				last_digit_sum = 2 if current_digit else 1
		print(a + '\n')
main()


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import PriorityQueue as pq
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, list(input()[:-1])))
	p = ['0'] * n
	p[0] = '1'
	c = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			p[i] = str(1 - int(p[i - 1]))
			c += 1
		else:
			if s[i] == 0:
				if c % 2:
					p[i] = '1'
				else:
					p[i] = '0'
			else:
				p[i] = '1'
			c = 1
	print(''.join(p))


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	k = '1'
	z = int(k[0]) + int(s[0])
	for i in range(1, len(s)):
		if int(s[i]) + 1 != z:
			k = k + '1'
			z = int(s[i]) + 1
		else:
			k = k + '0'
			z = int(s[i]) + 0
	print(k)


from __future__ import division, print_function
from itertools import permutations
import threading, bisect, math, heapq, sys
from collections import deque
from sys import stdin, stdout
i_m = 9223372036854775807

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
prime = []

def dfs(n, d, v):
	v[n] = 1
	x = d[n]
	for i in x:
		if i not in v:
			dfs(i, d, v)
	return p

def block(x):
	v = []
	while x > 0:
		v.append(int(x % 2))
		x = int(x / 2)
	ans = []
	for i in range(0, len(v)):
		if v[i] == 1:
			ans.append(2 ** i)
	return ans

def main():
	t = inin()
	for _ in range(t):
		n = inin()
		s = sin()
		s = list(s)
		for i in range(n):
			s[i] = int(s[i])
		if s[0] == 1:
			a = [2]
			b = [2 - s[0]]
		else:
			a = [1]
			b = [1]
		for i in range(1, n):
			p = q = 0
			for j in range(3):
				if j != a[-1] and (j - s[i] == 1 or j - s[i] == 0):
					p = j - s[i]
					q = j
			b.append(p)
			a.append(q)
		print(*b, sep='')

def intersection(l, r, ll, rr):
	if ll > r or rr < l:
		return 0
	else:
		l = max(l, ll)
		r = min(r, rr)
	return max(0, r - l + 1)
fac = []

def fact(n, mod):
	global fac
	fac.append(1)
	for i in range(1, n + 1):
		fac.append(fac[i - 1] * i % mod)
	f = fac[:]
	return f

def nCr(n, r, mod):
	global fac
	x = fac[n]
	y = fac[n - r]
	z = fac[r]
	x = moddiv(x, y, mod)
	return moddiv(x, z, mod)

def moddiv(m, n, p):
	x = pow(n, p - 2, p)
	return m * x % p

def GCD(x, y):
	x = abs(x)
	y = abs(y)
	if min(x, y) == 0:
		return max(x, y)
	while y:
		(x, y) = (y, x % y)
	return x

def Divisors(n):
	l = []
	ll = []
	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)
				ll.append(n // i)
	l.extend(ll[::-1])
	return l

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 prime

def primeFactors(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(i)
			n = n // i
	if n > 2:
		a.append(n)
	return a
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'R'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'R'[0]:
		A.append(sign * numb)
	return A
main()


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, list(input())))
	b.append(0)
	curr = 1
	a = []
	for i in range(n):
		a.append(str(curr))
		if b[i] + curr == 1:
			curr = b[i + 1]
		elif b[i] + curr == 0:
			curr = 1
		else:
			curr = 1 - b[i + 1]
	print(''.join(a))


import sys, math
sys.setrecursionlimit(10 ** 6)
fastinput = sys.stdin.readline
fastout = sys.stdout.write
t = int(fastinput())
while t:
	t -= 1
	n = int(input())
	s = input()
	result = ''
	ans = ''
	for i in range(n):
		if i == 0:
			if s[i] == '0':
				result = '1'
				ans += '1'
			else:
				result = '2'
				ans += '1'
		elif s[i] == '1' and result == '2':
			result = '1'
			ans += '0'
		elif s[i] == '1' and (result == '1' or result == '0'):
			result = '2'
			ans += '1'
		elif s[i] == '0' and result == '1':
			result = '0'
			ans += '0'
		else:
			result = '1'
			ans += '1'
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	b = input()
	a = ''
	d = ''
	if b[0] == '1':
		a += '1'
		d += '2'
	else:
		a += '1'
		d += '1'
	for i in range(1, n):
		if b[i] == '1':
			if d[-1] == '2':
				a += '0'
				d += '1'
			else:
				a += '1'
				d += '2'
		elif d[-1] == '1':
			a += '0'
			d += '0'
		else:
			a += '1'
			d += '1'
	print(a)


import math
for _ in range(int(input())):
	n = int(input())
	b = input()
	ans = ''
	prev = 'c'
	for i in range(n):
		if b[i] == '0':
			if prev == '1':
				ans += '0'
				prev = '0'
			else:
				ans += '1'
				prev = '1'
		elif prev == '2':
			ans += '0'
			prev = '1'
		else:
			ans += '1'
			prev = '2'
	print(ans)


for t in range(0, int(input())):
	n = int(input())
	b = input()
	a = '1'
	for i in range(1, len(b)):
		if int(a[i - 1]) + int(b[i - 1]) == 2:
			if b[i] == '1':
				a += '0'
			else:
				a += '1'
		if int(a[i - 1]) + int(b[i - 1]) == 1:
			if b[i] == '1':
				a += '1'
			else:
				a += '0'
		if int(a[i - 1]) + int(b[i - 1]) == 0:
			if b[i] == '1':
				a += '1'
			else:
				a += '1'
	print(a)


def main():
	for _ in range(int(input())):
		n = int(input())
		a = input()
		ans = ''
		prev = '0'
		for i in a:
			if i == '1' and prev != '2':
				ans += '1'
				prev = '2'
			elif i == '1' and prev == '2':
				ans += '0'
				prev = '1'
			elif i == '0' and prev != '1':
				ans += '1'
				prev = '1'
			elif i == '0' and prev == '1':
				ans += '0'
				prev = '0'
		print(ans)
main()


k = int(input())
while k > 0:
	n = int(input())
	l = input()
	last = -1
	s = ''
	for i in l:
		if i == '1' and last != 2:
			s = s + '1'
			last = 2
		elif i == '1' and last == 2:
			s = s + '0'
			last = 1
		elif i == '0' and last != 1:
			s = s + '1'
			last = 1
		elif i == '0' and last == 1:
			s = s + '0'
			last = 0
	print(s)
	k = k - 1


t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	s = '1'
	for j in range(1, len(b)):
		if b[j] == '0' and b[j - 1] == '1':
			if s[len(s) - 1] == '0':
				s += '0'
			else:
				s += '1'
		elif b[j] == '1' and b[j - 1] == '0':
			if s[len(s) - 1] == '0':
				s += '1'
			else:
				s += '1'
		elif b[j] == '0' and b[j - 1] == '0':
			if s[len(s) - 1] == '0':
				s += '1'
			else:
				s += '0'
		elif b[j] == '1' and b[j - 1] == '1':
			if s[len(s) - 1] == '0':
				s += '1'
			else:
				s += '0'
	print(s)


a = int(input())
for i in range(a):
	s = int(input())
	d = input()
	z = 0
	for i1 in range(s):
		if d[i1] == '1':
			if 1 + 1 != z:
				print('1', end='')
				z = 2
			else:
				print('0', end='')
				z = 1
		elif 0 + 1 != z:
			print('1', end='')
			z = 1
		else:
			print('0', end='')
			z = 0
	print('')


for i in range(int(input())):
	n = int(input())
	s = input()
	s2 = ''
	d = ''
	for i in s:
		if i == '1' and d != '2':
			s2 += '1'
			d = '2'
		elif i == '1' and d == '2':
			s2 += '0'
			d = '1'
		elif i == '0' and d != '1':
			s2 += '1'
			d = '1'
		elif i == '0' and d == '1':
			s2 += '0'
			d = '0'
	print(s2)


t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	ans = '1'
	d = str(int(ans) + int(b[0]))
	for i in range(1, n):
		if b[i] == '1':
			if d[-1] == '2':
				ans += '0'
				d += '1'
			else:
				ans += '1'
				d += '2'
		elif d[-1] == '2':
			ans += '1'
			d += '1'
		elif d[-1] == '1':
			ans += '0'
			d += '0'
		else:
			ans += '1'
			d += '1'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = input()
	ans = ''
	ps = 0
	for i in range(n):
		if i == 0:
			ans += '1'
			if b[i] == '0':
				ps = 1
			else:
				ps = 2
		elif b[i] == '0':
			if ps == 1:
				ans += '0'
				ps = 0
			else:
				ps = 1
				ans += '1'
		elif ps == 2:
			ans += '0'
			ps = 1
		else:
			ans += '1'
			ps = 2
	print(ans)


def fun(st, n):
	ans = ''
	prv_sum = None
	for (i, val) in enumerate(st):
		val = int(val)
		if val == 1:
			if prv_sum == None or prv_sum == 1 or prv_sum == 0:
				prv_sum = 2
				ans += '1'
				continue
			if prv_sum == 2:
				prv_sum = 1
				ans += '0'
				continue
		else:
			if prv_sum == 2 or prv_sum == None or prv_sum == 0:
				prv_sum = 1
				ans += '1'
				continue
			if prv_sum == 1:
				prv_sum = 0
				ans += '0'
	print(ans)
T = int(input())
for i in range(T):
	n = list(map(int, input().split()))
	ls = input()
	fun(ls, n)


for p in range(int(input())):
	n = int(input())
	b = input()
	b_list = [int(x) for x in str(b)]
	a = [1]
	s = [b_list[0] + 1]
	for i in range(1, n):
		q = b_list[i] + 1
		s.append(q)
		if s[i] == s[i - 1]:
			a.append(0)
			s[i] = b_list[i]
		else:
			a.append(1)
			s[i] = b_list[i] + 1
	listToStr = ''.join([str(elem) for elem in a])
	print(listToStr)


t = int(input())
for j in range(0, t):
	n = int(input())
	b = input()
	a = [0 for i in range(0, n)]
	a[0] = '1'
	last = 0
	if b[0] == '0':
		last = 1
	else:
		last = 2
	for i in range(1, n):
		if last == 2:
			if b[i] == '0':
				a[i] = '1'
				last = 1
			else:
				a[i] = '0'
				last = 1
		elif last == 1:
			if b[i] == '1':
				a[i] = '1'
				last = 2
			else:
				a[i] = '0'
				last = 0
		elif last == 0:
			if b[i] == '1':
				a[i] = '1'
				last = 2
			else:
				a[i] = '1'
				last = 1
	print(''.join(a))


for _ in range(int(input())):
	n = int(input())
	s = input()
	flag = False
	ans = '1'
	ls = int(s[0]) + 1
	for i in range(1, n):
		if 1 + int(s[i]) != ls:
			ans = ans + '1'
			ls = int(s[i]) + 1
		else:
			ans = ans + '0'
			ls = int(s[i]) + 0
	print(ans)


try:
	for t in range(int(input())):
		n = int(input())
		b = input()
		a = ''
		c = ''
		for j in range(0, n):
			if j == 0:
				a = a + '1'
				c = c + str(int(b[j]) + 1)
			elif int(b[j]) + 1 != int(c[j - 1]):
				a = a + '1'
				c = c + str(int(b[j]) + 1)
			else:
				a = a + '0'
				c = c + str(int(b[j]) + 0)
		print(a)
except EOFError as e:
	pass


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	c = input()
	ll = []
	ll.append('1')
	anss = []
	if c[0] == '1':
		anss.append('2')
	else:
		anss.append('1')
	for i in range(1, n):
		if c[i] == '0':
			if anss[-1] == '1':
				ll.append('0')
				anss.append('0')
			else:
				anss.append('1')
				ll.append('1')
		elif anss[-1] == '2':
			ll.append('0')
			anss.append('1')
		else:
			ll.append('1')
			anss.append('2')
	print(''.join(ll))


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
uu = t
while t > 0:
	t -= 1
	ans = ''
	n = fi()
	a = ii()
	prev = -1
	for i in range(n):
		if prev != 1 + int(a[i]):
			print(1, end='')
			prev = 1 + int(a[i])
		else:
			print(0, end='')
			prev = int(a[i])
	print(ans)


l = list
n = int(input())
for _ in range(n):
	s = '1'
	a = input()
	b = l(input())
	e = 1 + int(b[0])
	for k in b[1:]:
		if k == '1':
			if e == 0 or e == 1:
				s = s + '1'
				e = 2
			elif e == 2:
				s = s + '0'
				e = 1
		elif e == 0 or e == 2:
			s = s + '1'
			e = 1
		elif e == 1:
			s = s + '0'
			e = 0
	print(s)


for _ in range(int(input())):
	n = int(input())
	b = input()
	ans = ''
	s = 5
	for i in b:
		if int(i) + 1 != s:
			ans += '1'
			s = int(i) + 1
		else:
			ans += '0'
			s = int(i)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	w = '1'
	for i in range(n - 1):
		if w[i] == '1':
			if s[i] == '1':
				if s[i + 1] == '1':
					w += '0'
				else:
					w += '1'
			elif s[i + 1] == '1':
				w += '1'
			else:
				w += '0'
		elif s[i] == '1':
			if s[i + 1] == '1':
				w += '1'
			else:
				w += '0'
		else:
			w += '1'
	print(w)


import sys
input = sys.stdin.readline

def solve(n, b):
	a = '1'
	for i in range(1, n):
		if b[i] == '1':
			if a[i - 1] == '1' and b[i - 1] == '1':
				a += '0'
			else:
				a += '1'
		elif a[i - 1] == b[i - 1]:
			a += '1'
		else:
			a += '0'
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	b = sys.stdin.readline().rstrip()
	print(solve(n, b))


t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	ctr = 0
	res = []
	for j in range(n):
		if ctr == 2:
			if l[j] == '1':
				res.append(0)
				ctr = 1
			else:
				res.append(1)
				ctr = 1
		elif ctr == 1:
			if l[j] == '1':
				res.append(1)
				ctr = 2
			else:
				res.append(0)
				ctr = 0
		elif l[j] == '1':
			res.append(1)
			ctr = 2
		else:
			res.append(1)
			ctr = 1
	print(*res, sep='')


for _ in range(int(input())):
	n = int(input())
	b = tuple(map(int, list(input())))
	ans = '1'
	for i in range(1, n):
		if b[i - 1] + int(ans[-1]) == b[i] + 1:
			ans += '0'
		else:
			ans += '1'
	print(ans)


def main():
	t = int(input())
	while t != 0:
		n = int(input())
		b = input()
		(a, p) = ('', '?')
		for c in b:
			(x, d) = ('1', '2' if c == '1' else '1')
			if d == p:
				(x, d) = ('0', c)
			a += x
			p = d
		print(a)
		t -= 1
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	b = input().strip()
	a = '1'
	d = str(int(a[0]) + int(b[0]))
	for i in range(1, n):
		x = int(b[i]) + 1
		if x == int(d[-1]):
			a += '0'
			d += b[i]
		else:
			a += '1'
			d += str(int(b[i]) + 1)
	print(a)


t = int(input())
for _ in range(t):
	_ = int(input())
	b = list(map(int, list(input())))
	a = [1]
	for i in range(1, len(b)):
		if b[i] == b[i - 1]:
			if a[-1] == 1:
				a.append(0)
			else:
				a.append(1)
		elif b[i - 1] == 0 and b[i] == 1:
			a.append(1)
		elif b[i - 1] == 1 and b[i] == 0:
			if a[-1] == 0:
				a.append(0)
			else:
				a.append(1)
	print(''.join(map(str, a)))


t = int(input())
for q in range(t):
	n = int(input())
	b = input()
	a = [1]
	cur = 1
	for x in range(1, n):
		if cur == 1:
			if b[x] == '1' and b[x - 1] == '1':
				a.append(0)
				cur = 0
			elif b[x] == '0' and b[x - 1] == '1':
				a.append(1)
				cur = 1
			elif b[x] == '0' and b[x - 1] == '0':
				a.append(0)
				cur = 0
			elif b[x] == '1' and b[x - 1] == '0':
				a.append(1)
				cur = 1
		elif cur == 0:
			if b[x] == '1' and b[x - 1] == '1':
				a.append(1)
				cur = 1
			elif b[x] == '0' and b[x - 1] == '1':
				a.append(0)
				cur = 0
			elif b[x] == '0' and b[x - 1] == '0':
				a.append(1)
				cur = 1
			elif b[x] == '1' and b[x - 1] == '0':
				a.append(1)
				cur = 1
	for x in a:
		print(x, end='')
	print()


import sys, io, os
input = lambda : sys.stdin.readline().encode()
read = lambda : map(int, input().split())
out = []
for _ in range(int(input())):
	n = int(input())
	b = input().strip()
	a = []
	p = -1
	for i in b:
		if i == 49:
			if p != 2:
				a.append('1')
			else:
				a.append('0')
		elif p != 1:
			a.append('1')
		else:
			a.append('0')
		p = (a[-1] == '1') + (i == 49)
	out.append(''.join(a))
print('\n'.join(out))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	B = input().strip()
	prev = 0
	ans = ['1'] * n
	for i in range(n):
		curr = int(ans[i]) + int(B[i])
		if curr == prev:
			ans[i] = '0'
			curr -= 1
		prev = curr
	return ''.join(ans)
for _ in range(int(input())):
	print(solve())


import math
import collections

def solve(n, b):
	a = [1] * n
	b = [int(b[i]) for i in range(n)]
	for i in range(1, n):
		if a[i - 1] + b[i - 1] == 1 + b[i]:
			a[i] = 0
		else:
			a[i] = 1
	return ''.join([str(i) for i in a])
t = int(input())
for t in range(t):
	n = int(input())
	b = input()
	result = solve(n, b)
	print(result)


from sys import stdin, stdout
from sys import stdin, stdout
from math import ceil, gcd

def writ(ss):
	stdout.write(str(ss) + '\n')
for test in range(int(stdin.readline())):
	n = int(stdin.readline().strip())
	s = stdin.readline().strip()
	ans = ['1']
	d = [int(s[0]) + 1]
	for i in range(1, n):
		if 1 + int(s[i]) != d[-1]:
			ans.append('1')
			d.append(1 + int(s[i]))
		else:
			ans.append('0')
			d.append(0 + int(s[i]))
	writ(''.join(ans))


def getInput():
	n = int(input())
	b = input()
	return (n, b)

def calculateA(n, b):
	a = ''
	prev = ''
	for i in range(n):
		if i == 0:
			a += '1'
			prev = 1 + int(b[0])
		else:
			tmp = int(b[i]) + 1
			if tmp == prev:
				a += '0'
				prev = int(b[i])
			else:
				a += '1'
				prev = tmp
	return a
testCases = int(input())
while testCases:
	(n, b) = getInput()
	a = calculateA(n, b)
	print(a)
	testCases -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = ''
	last = 0
	for i in s:
		if i == '1':
			if last != 2:
				ans += '1'
				last = 2
			elif last != 1:
				ans += '0'
				last = 1
		elif last != 1:
			ans += '1'
			last = 1
		elif last != 0:
			ans += '0'
			last = 0
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	b = input()
	prev = 0
	a = ''
	for i in b:
		add = 1 + int(i)
		if add != prev:
			a = a + '1'
			prev = add
		else:
			a = a + '0'
			prev = int(i)
	print(a)


t = int(input().strip())
while t:
	n = int(input().strip())
	b = list(map(int, input().strip()))
	a = ['1']
	c = b[0] + int(a[0])
	for i in range(1, n):
		if b[i] == 1:
			if c == 2:
				a.append('0')
				c = 1
			else:
				a.append('1')
				c = 2
		elif c == 1:
			a.append('0')
			c = 0
		else:
			a.append('1')
			c = 1
	print(''.join(a))
	t -= 1


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	a = '1'
	c = 1 + int(b[0])
	for i in range(1, n):
		if b[i] == '0':
			if c == 1:
				a += '0'
				c = 0
			elif c == 2:
				a += '1'
				c = 1
			elif c == 0:
				a += '1'
				c = 1
		elif c == 1:
			a += '1'
			c = 2
		elif c == 2:
			a += '0'
			c = 1
		elif c == 0:
			a += '1'
			c = 2
	print(a)


try:
	for _ in range(int(input())):
		n = int(input())
		b = input()
		ans = '1'
		for i in range(1, n):
			if int(b[i - 1]) + int(ans[-1]) == int(b[i]) + 1:
				ans += '0'
			else:
				ans += '1'
		print(ans)
except:
	pass


def doTestcase():
	n = int(input())
	b = list(map(int, list(input())))
	a = [0] * n
	last = 0
	for i in range(n):
		a[i] = 1
		if a[i] + b[i] == last:
			a[i] = 0
		last = a[i] + b[i]
	print(*a, sep='')
t = int(input())
for _ in range(t):
	doTestcase()


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	b = input().strip()
	last = '0'
	d = ['1'] * n
	for i in range(n):
		if b[i] == '0':
			if last == '1':
				d[i] = '0'
				last = '0'
			else:
				d[i] = '1'
				last = '1'
		elif last == '1' or last == '0':
			d[i] = '1'
			last = '2'
		elif last == '2':
			d[i] = '0'
			last = '1'
	print(''.join(d))


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	s = input()
	p = 0
	a = 0
	for i in s:
		if 1 + int(i) == p:
			a = 0
		else:
			a = 1
		p = a + int(i)
		print(a, end='')
	print()


from sys import stdout
for _ in range(int(input())):
	n = int(input())
	b = input()
	last = -1
	if n == 1:
		print('1')
		continue
	s = ''
	for i in range(n):
		if int(b[i]) + 1 == last:
			s += '0'
			last = int(b[i])
		else:
			s += '1'
			last = int(b[i]) + 1
	stdout.write(s)
	print()


from collections import deque, defaultdict, Counter
import math
from sys import stdin, stdout
import sys

def inp():
	return int(stdin.readline())

def inlt():
	return list(map(int, stdin.readline().split()))

def insr():
	return list(stdin.readline().strip())

def invr():
	return map(int, stdin.readline().split())
from queue import Queue
q = Queue()
import itertools
global vis, dis, graph

def bfs(source_node, vis, graph, dis):
	q.put(source_node)
	vis[source_node] = True
	dis[source_node] = 0
	while not q.empty():
		current_node = q.get()
		for neighbour in graph[current_node]:
			if vis[neighbour] == False:
				q.put(neighbour)
				dis[neighbour] = dis[current_node] + 1
				vis[neighbour] = True
import math

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def main():
	for __ in range(inp()):
		n = inp()
		a = input()
		b = ['1' for _ in range(n)]
		bb = []
		for i in range(n):
			bb.append(int(a[i]) + int(b[i]))
		for i in range(1, n):
			if bb[i] == bb[i - 1]:
				b[i] = '0'
				bb[i] = int(a[i]) + int(b[i])
		print(''.join(b))
main()


import sys
input = sys.stdin.readline

def iin():
	return int(input())

def sin():
	return input().strip()

def nin():
	return map(int, sin().split())

def lin():
	return list(map(int, sin().split()))

def p(x):
	print(x)

def pl(l):
	for i in l:
		print(i, end=' ')

def pnl(l):
	pl(l)
	print()

def pyn(x):
	if x:
		print('YES')
	else:
		print('NO')
te = 1
te = iin()
while te > 0:
	n = iin()
	b = sin()
	a = '1'
	p = int(b[0]) + int(a)
	for i in b[1:]:
		if p == 2:
			if i == '1':
				a += '0'
			else:
				a += '1'
			p = 1
		elif p == 1:
			if i == '1':
				a += '1'
				p = 2
			else:
				a += '0'
				p = 0
		else:
			if i == '1':
				p = 2
			else:
				p = 1
			a += '1'
	print(a)
	te -= 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	b = input()
	a = [1] * n
	prev = 0
	ans = ''
	for i in range(n):
		s = int(b[i]) + a[i]
		if s == prev:
			a[i] = 1 - a[i]
		ans += str(a[i])
		prev = int(b[i]) + a[i]
	print(ans)


import sys
from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	pre = ''
	a = ''
	for j in range(n):
		if b[j] == '0' and pre == '1':
			a += '0'
			pre = '0'
		elif b[j] == '0' and pre != '1':
			a += '1'
			pre = '1'
		elif b[j] == '1' and pre == '2':
			a += '0'
			pre = '1'
		elif b[j] == '1' and pre != '2':
			a += '1'
			pre = '2'
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(input())
	a = ['1']
	for i in range(1, n):
		if b[i] != b[i - 1]:
			if b[i - 1] == a[i - 1]:
				a.append('1')
			else:
				a.append(a[i - 1])
		else:
			a.append('0' if a[i - 1] == '1' else '1')
	print(''.join(a))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	r = 0
	re = ''
	if s[0] == '1':
		re += '1'
		r = 2
	else:
		re += '1'
		r = 1
	for i in range(1, len(s)):
		if r == 2:
			if s[i] == '1':
				re += '0'
			else:
				re += '1'
			r = 1
		elif r == 1:
			if s[i] == '1':
				r = 2
			else:
				r = 0
			re += s[i]
		else:
			if s[i] == '1':
				r = 2
			else:
				r = 1
			re += '1'
	print(re)


for ii in range(int(input())):
	n = int(input())
	a = input()
	(s, x) = ('', 0)
	for jj in range(n):
		if x == 0:
			if a[jj] == '0':
				s += '1'
				x = 1
			else:
				s += '1'
				x = 2
		elif x == 2:
			if a[jj] == '0':
				s += '1'
				x = 1
			else:
				s += '0'
				x = 1
		elif a[jj] == '0':
			s += '0'
			x = 0
		else:
			s += '1'
			x = 2
	print(s)


tests = int(input())
for q in range(tests):
	n = int(input())
	d = input()
	ans = ''
	s = ''
	l = 3
	for i in range(n):
		mx = int(d[i]) + 1
		if l == mx:
			k = int(d[i])
		else:
			k = int(d[i]) + 1
		l = k
		s += str(k)
	for i in range(n):
		ans += str(int(s[i]) - int(d[i]))
	print(ans)


def solve():
	n = int(input())
	string = input()
	output = '1'
	prev = int(string[0]) + 1
	for i in range(1, n):
		if string[i] == '1':
			if prev == 1:
				output += '1'
				prev = 2
			elif prev == 2:
				output += '0'
				prev = 1
			elif prev == 0:
				output += '1'
				prev = 2
		elif prev == 2:
			output += '1'
			prev = 1
		elif prev == 1:
			output += '0'
			prev = 0
		elif prev == 0:
			output += '1'
			prev = 1
	print(output)
	return
t = int(input())
while t != 0:
	solve()
	t -= 1