C. Ternary XOR
greedy; implementation
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.
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\)).
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.