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
#include <bits/stdc++.h>
using namespace std;
char local = 'O';
template <typename T>
void read(T &a) {
  cin >> a;
}
template <typename T, typename T1>
void read(T &a, T1 &b) {
  cin >> a >> b;
}
template <typename T, typename T1, typename T2>
void read(T &a, T1 &b, T2 &c) {
  cin >> a >> b >> c;
}
template <typename T, typename T1>
void read(pair<T, T1> &p) {
  cin >> p.first >> p.second;
}
template <typename T>
void read(T arr[], long long int n) {
  for (long long int i = 0; i < n; i++) {
    read(arr[i]);
  }
}
template <typename T>
void read(vector<T> &arr) {
  for (long long int i = 0; i < arr.size(); i++) {
    read(arr[i]);
  }
}
long long int modularExponentiation(long long int x, long long int n,
                                    long long int M) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return modularExponentiation((x * x) % M, n / 2, M);
  return (x * modularExponentiation((x * x) % M, (n - 1) / 2, M)) % M;
}
long long int binaryExponentiation(long long int x, long long int n) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return binaryExponentiation(x * x, n / 2);
  else
    return x * binaryExponentiation(x * x, (n - 1) / 2);
}
long long int GCD(long long int A, long long int B) {
  if (B == 0)
    return A;
  else
    return GCD(B, A % B);
}
long long int extended_GCD(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int modPrimeInverse(long long int A, long long int M) {
  return modularExponentiation(A, M - 2, M);
}
void sieve(long long int N) {
  bool isPrime[N + 1];
  for (long long int i = 0; i <= N; ++i) {
    isPrime[i] = true;
  }
  isPrime[0] = false;
  isPrime[1] = false;
  for (long long int i = 2; i * i <= N; ++i) {
    if (isPrime[i] == true) {
      for (long long int j = i * i; j <= N; j += i) isPrime[j] = false;
    }
  }
}
void factorSieve(long long int n) {
  long long int minPrime[n + 1];
  memset(minPrime, 0, sizeof(minPrime));
  for (long long int i = 2; i * i <= n; ++i) {
    if (minPrime[i] == 0) {
      for (long long int j = i * i; j <= n; j += i) {
        if (minPrime[j] == 0) {
          minPrime[j] = i;
        }
      }
    }
  }
  for (long long int i = 2; i <= n; ++i) {
    if (minPrime[i] == 0) {
      minPrime[i] = i;
    }
  }
}
vector<long long int> factorize(long long int n, long long int minPrime[]) {
  vector<long long int> res;
  while (n != 1) {
    res.push_back(minPrime[n]);
    n /= minPrime[n];
  }
  return res;
}
void merge(long long int A[], long long int start, long long int mid,
           long long int end) {
  long long int p = start, q = mid + 1;
  long long int Arr[end - start + 1], k = 0;
  for (long long int i = start; i <= end; i++) {
    if (p > mid)
      Arr[k++] = A[q++];
    else if (q > end)
      Arr[k++] = A[p++];
    else if (A[p] < A[q])
      Arr[k++] = A[p++];
    else
      Arr[k++] = A[q++];
  }
  for (long long int p = 0; p < k; p++) {
    A[start++] = Arr[p];
  }
}
void merge_sort(long long int A[], long long int start, long long int end) {
  if (start < end) {
    long long int mid = (start + end) / 2;
    merge_sort(A, start, mid);
    merge_sort(A, mid + 1, end);
    merge(A, start, mid, end);
  }
}
long long int binarySearch(long long int a[], long long int low,
                           long long int high, long long int key) {
  while (low <= high) {
    long long int mid = (low + high) / 2;
    if (a[mid] < key) {
      low = mid + 1;
    } else if (a[mid] > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}
bool sortbysec(const pair<long long int, long long int> &a,
               const pair<long long int, long long int> &b) {
  if (a.first == b.first) {
    a.second > b.second;
  }
  return (a.first < b.first);
}
long long int a[100000];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    string x;
    long long int n;
    cin >> n;
    cin >> x;
    long long int f = 0;
    string ans1 = "";
    string ans2 = "";
    for (auto i : x) {
      if (f == 0) {
        ans1 += '1';
        ans2 += '1';
        f = 1;
      } else {
        if (i == '2' && f == 1) {
          ans1 += '1';
          ans2 += '1';
        } else if (i == '2' && f == 2) {
          ans1 += '0';
          ans2 += '2';
        } else if (i == '0') {
          ans1 += '0';
          ans2 += '0';
        } else {
          if (f == 1) {
            ans1 += '1';
            ans2 += '0';
            f = 2;
          } else {
            ans1 += '0';
            ans2 += '1';
          }
        }
      }
    }
    cout << ans1 << "\n" << ans2 << "\n";
  }
}
