for _ in range(int(input())):
l, n = int(input()), input()
a, b = "1", "1"
trig = False
for i in range(1, l):
if n[i] == "0":
a += "0"
b += "0"
elif trig == False:
if n[i] == "2":
a += "1"
b += "1"
else:
a += "1"
b += "0"
trig = True
else:
b += n[i]
a += "0"
print(a)
print(b)
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
void solve() {
int n;
cin >> n;
string s;
cin >> s;
// https://codeforces.com/blog/entry/75246
/* 21211
a = 1 b = 1
a = 1 b = 0 , b = 2 , b = 1 , b = 1
*/
string a(n,'0'),b(n,'0');
for(int i =0;i<n;i++) {
if(s[i] == '1') {
a[i] = '1';
b[i] = '0';
for(int j = i+1;j<n;j++) {
b[j] = s[j];
}
break;
} if(s[i] == '0') {
a[i] = b[i] = '0';
} if(s[i] == '2') {
a[i] = b[i] = '1';
}
}
cout << a << endl << b << endl;
}
int32_t main() {
#ifdef Shirish
freopen("/home/shirish2601/input.txt", "r", stdin);
freopen("/home/shirish2601/output.txt", "w",stdout);
#endif
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
102. Binary Tree Level Order Traversal | 96. Unique Binary Search Trees |
75. Sort Colors | 74. Search a 2D Matrix |
71. Simplify Path | 62. Unique Paths |
50. Pow(x, n) | 43. Multiply Strings |
34. Find First and Last Position of Element in Sorted Array | 33. Search in Rotated Sorted Array |
17. Letter Combinations of a Phone Number | 5. Longest Palindromic Substring |
3. Longest Substring Without Repeating Characters | 1312. Minimum Insertion Steps to Make a String Palindrome |
1092. Shortest Common Supersequence | 1044. Longest Duplicate Substring |
1032. Stream of Characters | 987. Vertical Order Traversal of a Binary Tree |
952. Largest Component Size by Common Factor | 212. Word Search II |
174. Dungeon Game | 127. Word Ladder |
123. Best Time to Buy and Sell Stock III | 85. Maximal Rectangle |
84. Largest Rectangle in Histogram | 60. Permutation Sequence |
42. Trapping Rain Water | 32. Longest Valid Parentheses |
Cutting a material | Bubble Sort |