A number is ternary if it contains only digits $0$, $1$ and $2$. For example, the following numbers are ternary: $1022$, $11$, $21$, $2002$.

You are given a long ternary number $x$. The first (leftmost) digit of $x$ is guaranteed to be $2$, the other digits of $x$ can be $0$, $1$ or $2$.

Let's define the ternary XOR operation $\odot$ of two ternary numbers $a$ and $b$ (both of length $n$) as a number $c = a \odot b$ of length $n$, where $c_i = (a_i + b_i) \% 3$ (where $\%$ is modulo operation). In other words, add the corresponding digits and take the remainders of the sums when divided by $3$. For example, $10222 \odot 11021 = 21210$.

Your task is to find such ternary numbers $a$ and $b$ both of length $n$ and both without leading zeros that $a \odot b = x$ and $max(a, b)$ is the minimum possible.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow. The first line of the test case contains one integer $n$ ($1 \le n \le 5 \cdot 10^4$) — the length of $x$. The second line of the test case contains ternary number $x$ consisting of $n$ digits $0, 1$ or $2$. It is guaranteed that the first digit of $x$ is $2$. It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^4$ ($\sum n \le 5 \cdot 10^4$).


-----Output-----

For each test case, print the answer — two ternary integers $a$ and $b$ both of length $n$ and both without leading zeros such that $a \odot b = x$ and $max(a, b)$ is the minimum possible. If there are several answers, you can print any.


-----Example-----
Input
4
5
22222
5
21211
1
2
9
220222021

Output
11111
11111
11000
10211
1
1
110111011
110111010

Difficulty: introductory

Starter code:

Solutions:
for _ in range(int(input())):
    n=int(input())
    s=input()
    a=""
    b=""
    flag=1
    for i in s:
        if flag:
            if i=="2":
                a+="1"
                b+="1"
            elif i=="1":
                a+="1"
                b+="0"
                flag=0
            else:
                a+="0"
                b+="0"
        else:
            if i=="2":
                a+="0"
                b+="2"
            elif i=="1":
                a+="0"
                b+="1"
                flag=0
            else:
                a+="0"
                b+="0"
    print(a)
    print(b)

import sys
input = lambda : sys.stdin.readline().strip()
ipnut = input
def main(t = 1):
    for i in range(t):
        n = int(input())
        a = []
        b = []
        s = list(map(int,input()))
        f = False
        for i in s:
            if i==0:
                a.append(0)
                b.append(0)
            elif i == 1 and not f:
                a.append(1)
                b.append(0)
                f = True
            elif i == 1:
                a.append(0)
                b.append(1)
            elif f:
                a.append(0)
                b.append(2)
            else:
                a.append(1)
                b.append(1)
        print(''.join(map(str,a)))
        print(''.join(map(str,b)))

main(int(input()))


import sys
input = lambda: sys.stdin.readline().rstrip()

def calc(S):
    f = 0
    A = []
    B = []
    for s in S:
        a = int(s)
        if a == 1:
            if f:
                A.append("0")
                B.append("1")
            else:
                f = 1
                A.append("1")
                B.append("0")
        if a == 0:
            A.append("0")
            B.append("0")
        if a == 2:
            if f:
                A.append("0")
                B.append("2")
            else:
                A.append("1")
                B.append("1")
    print("".join(A))
    print("".join(B))

T = int(input())
for _ in range(T):
    N = int(input())
    calc(input())


t = int(input())
for case_num in range(t):
    n = int(input())
    x = input()
    a = []
    b = []
    split = False
    for i in x:
        if not split:
            if i == '2':
                a.append('1')
                b.append('1')
            if i == '0':
                a.append('0')
                b.append('0')
            if i == '1':
                a.append('1')
                b.append('0')
                split = True
        else:
            a.append('0')
            b.append(i)
    print(''.join(a))
    print(''.join(b))


t = int(input())
for case_num in range(t):
    n = int(input())
    x = input()
    a = []
    b = []
    split = False
    for i in x:
        if not split:
            if i == '2':
                a.append('1')
                b.append('1')
            if i == '0':
                a.append('0')
                b.append('0')
            if i == '1':
                a.append('1')
                b.append('0')
                split = True
        else:
            a.append('0')
            b.append(i)
    print(''.join(a))
    print(''.join(b))


#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    t = I()
    for _ in range(t):
        n = I()
        x = list(map(int, input()))
        a = []
        b = []
        f = 0
        for i in x:
            if not i:
                a.append(0)
                b.append(0)
            elif i == 2:
                if f:
                    a.append(0)
                    b.append(2)
                else:
                    a.append(1)
                    b.append(1)
            else:
                if f:
                    a.append(0)
                    b.append(1)
                else:
                    a.append(1)
                    b.append(0)
                    f = 1
        print(*a,sep = "")
        print(*b,sep = "")
    return

#Solve
def __starting_point():
    solve()

__starting_point()

q = int(input())
for _ in range(q):
    input()
    x = input()
    ans1 = ['1']
    ans2 = ['1']
    is_one = False

    for i in x[1:]:
        if i == '0':
            ans1.append('0')
            ans2.append('0')
        elif i == '1':
            if is_one:
                ans1.append('0')
                ans2.append('1')
            else:
                ans1.append('1')
                ans2.append('0')
                is_one = True
        else:
            if is_one:
                ans1.append('0')
                ans2.append('2')
            else:
                ans1.append('1')
                ans2.append('1')
    for i in ans1:
        print(i, end='')
    print()
    for i in ans2:
        print(i, end='')
    print()


for _ in range(int(input())):
    n = int(input())
    number = input()
    a = []
    b = []
    flag = 0
    for c in number:
        if c == '2':
            if flag == 0:
                a.append('1')
                b.append('1')
            else:
                b.append('2')
                a.append('0')
        elif c == '0':
            a.append('0')
            b.append('0')
        else:
            if flag == 0:
                a.append('1')
                b.append('0')
                flag = 1
            else:
                a.append('0')
                b.append('1')
            
    print(''.join(a))
    print(''.join(b))

for tc in range(int(input())):
    n = int(input())
    s = input()
    ch = 0
    a = ''
    b = ''
    for c in s:
        if c == '2':
            if ch:
                a += '0'
                b += '2'
            else:
                a += '1'
                b += '1'
        elif c == '1':
            if ch:
                a += '0'
                b += '1'
            else:
                ch = 1
                a += '1'
                b += '0'
        else:
            a += '0'
            b += '0'
    print(a)
    print(b)
        


from math import *
t = int(input())
for y in range(t):
	n = int(input())
	s = input()
	f = 0
	a = ''
	b = ''
	for i in s:
		if f == 0:
			if i == '2':
				a += '1'
				b += '1'
			elif i == '1':
				a += '1'
				b += '0'
				f = 1
			else:
				a += '0'
				b += '0'
		else:
			if i == '2':
				a += '0'
				b += '2'
			elif i == '1':
				a += '0'
				b += '1'
			else:
				a += '0'
				b += '0'
	print(a)
	print(b)

import sys
def input():
	return sys.stdin.readline()[:-1]
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a, b = "", ""
	one = False
	for i in range(n):
		if s[i] == "0":
			a += "0"
			b += "0"
		elif s[i] == "1":
			if not one:
				a += "1"
				b += "0"
				one = True
			else:
				a += "0"
				b += "1"
		else:
			if not one:
				a += "1"
				b += "1"
			else:
				a += "0"
				b += "2"
	print(a)
	print(b)

def go():
    # n,k = map(int,input().split())

    n = int(input())
    x= input()
    a=[]
    b=[]
    i=0
    while i<n and x[i]!='1':
        if x[i]=='2':
            a.append('1')
            b.append('1')
        else:
            a.append('0')
            b.append('0')
        i+=1

    if i<n:
        a.append('1')
        b.append('0')
        i+=1

    while i<n:
        a.append('0')
        b.append(x[i])
        i+=1

    return ''.join(a) + '\n' + ''.join(b)





# x,s = map(int,input().split())
t = int(input())
# t=1
ans=[]
for _ in range(t):
    # go()
    ans.append(str(go()))

print('\n'.join(ans))

t = int(input())
for _ in range(t):
    n = int(input())
    x = input().strip()
    flag = False
    ans1 = ""
    ans2 = ""
    for c in x:
        if c=='0':
            ans1+='0'
            ans2+='0'
        elif flag:
            ans1+='0'
            ans2+=c
        elif c=='1':
            ans1+='1'
            ans2+='0'
            flag = True
        else:
            ans1+='1'
            ans2+='1'
    print(ans1)
    print(ans2)

tc = int(input())
for _ in range(tc):
    n = int(input())
    s = input()
    a = b = '1'
    flag = None
    for i in s[1:]:
        if int(i) % 2 == 0 and not flag:
            num = int(i) // 2
            a += str(num)
            b += str(num)
        else:
            num = int(i) // 2
            if not flag:
                a += str(num + 1)
                b += str(num)
                flag = True
            else:
                a += str(0)
                b += str(i)
    print(a, b, sep="\n")


t = int(input())

for _ in range(t):
    n = int(input())
    
    x = list(map(int, input()))
    
    a_larger = False
    
    a = []
    b = []
    for d in x:
        if a_larger:
            a += ["0"]
            b += [str(d)]
        else:
            if d==0:
                a += ["0"]
                b += ["0"]
            elif d==1:
                a += ["1"]
                b += ["0"]
                a_larger = True
            else:
                a += ["1"]
                b += ["1"]
    print("".join(a))
    print("".join(b))