如果一个数字仅包含数字 $$$0$$$、$$$1$$$ 和 $$$2$$$,则该数字是三进制的。例如,以下数字是三元:$$$1022$$$、$$$11$$$、$$$21$$$、$$$2002$$$。
给你一个长三进制数$$$x$$$。 $$$x$$$ 的第一个(最左边)数字保证为 $$$2$$$,$$$x$$$ 的其他数字可以是 $$$0$$$、$$$1$$$ 或 $$$2$$$。
让我们将两个三元数 $$$a$$$ 和 $$$b$$$(长度均为 $$$n$$$)的三元异或运算 $$$\odot$$$ 定义为数字 $$$c = a \odot b$$$,长度为 $$$n$$$,其中 $$$c_i = (a_i + b_i) \% 3$$$ (其中$$$\%$$$ 是模运算)。换句话说,将相应的数字相加,然后除以 $$$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$$$ 的长度。测试用例的第二行包含三进制数 $$$x$$$,由 $$$n$$$ 数字 $$$0、1$$$ 或 $$$2$$$ 组成。保证 $$$x$$$ 的第一位数字是 $$$2$$$。保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^4$$$ ($$$\sum n \le 5 \cdot 10^4$$$)。
输出
对于每个测试用例,打印答案 - 两个三元整数 $$$a$$$ 和 $$$b$$$ 长度均为 $$$n$$$ 并且都没有前导零,使得 $$$a \odot b = x$$$ 和 $$$max(a, b)$$$ 是可能的最小值。如果有多个答案,您可以打印任何一个。
示例
输入 #1
4 5 22222 5 21211 1 2 9 220222021
输出 #1
11111 11111 11000 10211 1 1 110111011 110111010