说明

时间限制：1 Sec 内存限制：256 MB 输入文件：xor.in 输出文件：xor.out

我们知道，三进制数包含三种数码：$0$、$1$、$2$。

现在来定义三进制下的异或运算 $\odot$：对于任意两个三进制数位 $a$ 和 $b$，$a \odot b=(a+b)\%3$，即 $a$、$b$ 之和除以 $3$ 的余数。

而两个三进制数 $a$ 和 $b$ 的异或计算，就是各自的三进制形态最低位对齐（位数不同则高位补零后对齐），按位依次进行异或计算，再合并为三进制数（与二进制数的位运算规则一致）。

例如：$110222 \odot 1021=111210$。

现在小明得到一个三进制数 $x$，最高位保证是 $2$。他需要找到两个三进制数 $a$ 和 $b$，使得：

• $a$ 和 $b$ 的位数一样多（不含前导 $0$）
• $a \odot b=x$

在所有满足条件的 $(a,b)$ 中，$max(a,b)$ 最小时，$a$ 和 $b$ 分别是多少？

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 行，每行一个三进制数 $x$，第 $i$ 行为第 $i$ 组询问。

输出格式

$t$ 组，每组 $2$ 行，第 $i$ 组输出为对第 $i$ 组询问的回答，即对应的 $max(a,b)$ 取最小值时，$a$、$b$ 分别是多少，两个数各占一行。如果两个数不相等，大的那个数先输出。

样例

样例 1

4
2
22222
21211
220222021

1
1
11111
11111
11000
10211
110111011
110111010

样例说明：$4$ 组询问满足要求的 $(a,b)$ 依次如下：

$2=1 \odot 1$

$22222=11111 \odot 11111$

$21211=11000 \odot 10211$

$220222021=110111011 \odot 110111010$

数据范围

$1 \le t \le 10^4$

令 $|x|$ 表示字符串 $x$ 的位数，有 $1 \le |x| \le 5 \times 10^4$

题目保证所有的 $|x|$ 之和不超过 $5 \times 10^4$。