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 ⊙ of two ternary numbers a and b (both of length n) as a number c = a ⊙ 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 ⊙ 11021 = 21210.

Your task is to find such ternary numbers a and b both of length n and both without leading zeros that a ⊙ 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 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow. The first line of the test case contains one integer n (1 ≤ n ≤ 5 ⋅ 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 ⋅ 10^4 (∑ n ≤ 5 ⋅ 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 ⊙ 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
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.List;
/**
 * Using FastReader and Output Class
 *
 * @author Wallace
 */
 public  class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        IAMBACK solver = new IAMBACK();
        solver.solve(1, in, out);
        out.close();
    }
    static class IAMBACK {
    
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            
             int t=in.nextInt();
             while(t!=0){
                int n=in.nextInt();
                String s=in.nextString();
                StringBuilder ans=new StringBuilder("");
                StringBuilder ans1=new StringBuilder("");
                int i=1;
                for(i=0;i<n;i++){
                    if(s.charAt(i)=='1'){
                        ans.append("0");
                        ans1.append("1");
                        break;
                    }else if(s.charAt(i)=='2'){
                        ans.append("1");
                        ans1.append("1");
                    }else{
                        ans.append("0");
                        ans1.append("0");
                    }

                }
                for(int j=i+1;j<n;j++){
                    ans1.append("0");

                     ans.append(s.charAt(j)+"");
                }
                out.println(ans.toString());
                out.println(ans1.toString());
                 t--;
             }
             
           
        }
        // public static long helper(long base, long exp){
        //     base %= MOD;
        //     long ret = 1;
        //     while (exp > 0) {
        //         if ((exp & 1) == 1) ret = ret * base % MOD;
        //         base = base * base % MOD;
        //         exp >>= 1;
        //     }
        //     return ret;
        // }

        

public static boolean next_permutation(long[] p) {
    for (int a = p.length - 2; a >= 0; --a)
      if (p[a] < p[a + 1])
        for (int b = p.length - 1;; --b)
          if (p[b] > p[a]) {
            long t = p[a];
            p[a] = p[b];
            p[b] = t;
            for (++a, b = p.length - 1; a < b; ++a, --b) {
              t = p[a];
              p[a] = p[b];
              p[b] = t;
            }
            return true;
          }
    return false;
  }



    }
    static class Permutation{
    // simply prints all permutation - to see how it works
	private static void printPermutations( Comparable[] c ) {
		System.out.println( Arrays.toString( c ) );
		while ( ( c = nextPermutation( c ) ) != null ) {
			System.out.println( Arrays.toString( c ) );
		}
	}

	// modifies c to next permutation or returns null if such permutation does not exist
	private static Comparable[] nextPermutation( final Comparable[] c ) {
		// 1. finds the largest k, that c[k] < c[k+1]
		int first = getFirst( c );
		if ( first == -1 ) return null; // no greater permutation
		// 2. find last index toSwap, that c[k] < c[toSwap]
		int toSwap = c.length - 1;
		while ( c[ first ].compareTo( c[ toSwap ] ) >= 0 )
			--toSwap;
		// 3. swap elements with indexes first and last
		swap( c, first++, toSwap );
		// 4. reverse sequence from k+1 to n (inclusive) 
		toSwap = c.length - 1;
		while ( first < toSwap )
			swap( c, first++, toSwap-- );
		return c;
	}

	// finds the largest k, that c[k] < c[k+1]
	// if no such k exists (there is not greater permutation), return -1
	private static int getFirst( final Comparable[] c ) {
		for ( int i = c.length - 2; i >= 0; --i )
			if ( c[ i ].compareTo( c[ i + 1 ] ) < 0 )
				return i;
		return -1;
	}

	// swaps two elements (with indexes i and j) in array 
	private static void swap( final Comparable[] c, final int i, final int j ) {
		final Comparable tmp = c[ i ];
		c[ i ] = c[ j ];
		c[ j ] = tmp;
	}
    }
    // for the fastreader
    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int pnumChars;
        

        public static int[] sieve;
        public static ArrayList<Integer> primes;
    
        public void setSieve(int MAXN) {
            primes = new ArrayList<>();
            sieve = new int[MAXN];
            int i, j;
            for (i = 2; i < MAXN; ++i)
                if (sieve[i] == 0) {
                    primes.add(i);
                    for (j = i; j < MAXN; j += i) {
                        sieve[j] = i;
                    }
                }
        }
        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        private int pread() {
            if (pnumChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= pnumChars) {
                curChar = 0;
                try {
                    pnumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (pnumChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = pread();
            }
            int res = 0;
            do {
                if (c == ',') {
                    c = pread();
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = pread();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String next() {
            return nextString();
        }

        public String nextString() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = pread();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String[] nextStringArray(int n)
        {
            String array[]=new String[n];
            for(int i=0;i<n;i++)
            {
                array[i]=nextString();
            }
            return array;
        }
        public long[] nextLongArray(int n) {
            long[] array = new long[n];
            for (int i = 0; i < n; i++) {
                array[i] = nextLong();
            }
            return array;
        }

        // pcwallace
        public double[] nextDoubleArray(int n) {
            double[] array = new double[n];
            for (int i = 0; i < n; i++) {
                array[i] = nextDouble();
            }
            return array;
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        public long nextLong() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = pread();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = pread();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = pread();
            }
            double res = 0.0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = pread();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}