众所周知，Rikka 不擅长数学。她的男朋友 Yuta 对此感到担忧，因此他给 Rikka 出了一道有趣的数学题来练习。

给定一个非负整数 $x$，Rikka 需要找到三个非负整数 $a, b, c$，满足以下三个条件：

1. $a + b = x$；
2. $\text{str}(c)$ 是 $\text{str}(a)$ 的子序列；
3. $\text{str}(c)$ 是 $\text{str}(b)$ 的子序列。

$\text{str}(d)$ 表示整数 $d$ 的十进制字符串表示。例如，$\text{str}(0) = \text{“0”}$，$\text{str}(103) = \text{“103”}$。 字符串 $s = s_1 \dots s_n$ 是字符串 $t = t_1 \dots t_m$ 的子序列，当且仅当存在一个下标序列 $1 \le i_1 < i_2 < \dots < i_n \le m$，满足对于所有 $j \in [1, n]$，都有 $s_j = t_{i_j}$。

为了避免无解的情况，Yuta 假设存在一种特殊的选择 “$-$” 作为 $c$，其中 $\text{str}(-)$ 等于空字符串。在此假设下，$a = 0, b = 9, c = -$ 成为 $x = 9$ 的一个合法解。

找到一个合法解对 Rikka 来说很容易。因此，Rikka 想要增加难度：她希望你找到一个合法解 $(a, b, c)$，使得 $\text{str}(c)$ 的长度尽可能大。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $x$ ($|\text{str}(x)| \le 5000$)。 输入保证 $\sum |\text{str}(x)| \le 10^5$。

输出格式

对于每个测试用例，输出三行，每行一个整数，分别代表 $a, b, c$。 如果存在多个最优解，输出其中任意一个即可。

样例

样例输入 1

3
2290283839620
1
9999999

样例输出 1

1145141919810
1145141919810
1145141919810
0
1
-
4545454
5454545
454545