CF1328C.Ternary XOR

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.

一个数被称为三进制数，当且仅当它仅由数字 $0$、$1$ 和 $2$ 组成。例如，以下数均为三进制数：$1022$、$11$、$21$、$2002$。

给定一个长度很长的三进制数 $x$。已知 $x$ 的首位（最左侧）数字必定为 $2$，其余各位可为 $0$、$1$ 或 $2$。

我们定义两个等长（长度均为 $n$）的三进制数 $a$ 和 $b$ 的三进制异或运算 $\odot$ 为一个长度为 $n$ 的三进制数 $c = a \odot b$，其中第 $i$ 位满足 $c_i = (a_i + b_i) \% 3$（$\%$ 表示取模运算）。换言之，将对应位上的数字相加，再对 $3$ 取余。例如，$10222 \odot 11021 = 21210$。

你的任务是找出两个长度均为 $n$、且均无前导零的三进制数 $a$ 和 $b$，使得 $a \odot b = x$，并使 $\max(a, b)$ 尽可能小。

你需要回答 $t$ 个相互独立的测试用例。

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$).

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^4$），表示三进制数 $x$ 的长度。每个测试用例的第二行包含一个由 $n$ 位数字 $0$、$1$ 或 $2$ 组成的三进制数 $x$。保证 $x$ 的第一位数字为 $2$。保证所有测试用例的 $n$ 值之和不超过 $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.

对于每个测试用例，输出答案——两个长度均为 $n$ 且均无前导零的三进制整数 $a$ 和 $b$，使得 $a \odot b = x$，且 $\max(a, b)$ 尽可能小。若存在多个满足条件的答案，输出任意一个即可。