1328C · Ternary XOR

Problem: 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 Format: 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 Format: 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.