题目描述

每个测试的时间限制：1 秒
每个测试的内存限制：256 兆字节

如果一个数只包含数字 $0$、$1$ 和 $2$，则称它为三进制数。例如，以下数是三进制数：$1022$、$11$、$21$、$2002$。

你得到一个很长的三进制数 $x$。$x$ 的第一位（最左边）保证是 $2$，其余位可以是 $0$、$1$ 或 $2$。

定义两个三进制数 $a$ 和 $b$（长度均为 $n$）的三进制异或运算 $a \odot b$ 为长度 $n$ 的数 $c$，其中 $c_i = (a_i + b_i) \bmod 3$（$\bmod$ 表示取模运算）。换句话说，将对应位相加，然后取和除以 $3$ 的余数。例如，$10222 \odot 11021 = 21210$。

你的任务是找到两个三进制数 $a$ 和 $b$，长度均为 $n$，都没有前导零，满足 $a \odot b = x$，并且 $\max(a, b)$ 尽可能小。

如果有多个答案，输出任意一组即可。

你需要回答 $t$ 组独立的测试用例。

输入格式

第一行包含一个整数 $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$）。

输出格式

对于每个测试用例，输出答案 —— 两个三进制数 $a$ 和 $b$，长度均为 $n$，且都没有前导零，使得 $a \odot b = x$，并且 $\max(a, b)$ 尽可能小。如果有多个答案，输出任意一组即可。

4
5
22222
5
21211
1
2
9
220222021

11111
11111
11000
10211
1
1
110111011
110111010