图片来自维基共享资源 cc by-sa 3.0

如果你熟悉《2048》这款游戏，这个题目可能会很容易理解。

无论如何，我们将定义我们自己的一维版本游戏：

给你一个仅包含 2 的幂的数字列表。你可以通过向右“推送”（push）来“压缩”这个列表。如果两个相同的数字相邻，推送会导致它们合并。这里的“合并”（merge）意味着这两个数字被它们的和所代替。每个数字只能合并一次——如果它可以与左右相邻的数字合并，它会与右侧的数字合并。这个过程是从右向左进行评估的。例如，列表 $[2, 2, 2, 2]$ 在一次推送后将变为 $[4, 4]$。再比如，给定列表 $[2, 2, 2]$，在一次推送后，我们得到一个新列表 $[2, 4]$，并且我们无法通过“推送”进一步改变它。

现在，其中一些列表在经过若干次推送后，可能会变成只剩一个元素。例如：$[8, 2, 2, 4] \Rightarrow [8, 4, 4] \Rightarrow [8, 8] \Rightarrow [16]$。

如果一个列表仅通过“推送”就能缩减为只含单个元素的列表，我们称这样的列表是美妙的（nice）。

你的任务是，通过向给定的列表中插入若干个（可以是零个）来自 $\{2, 4, 8\}$ 的元素，使其变成一个美妙的列表。为了使问题稍微简单一些，初始列表只能包含集合 $\{2, 4, 8\}$ 中的数字。

输入格式

输入的第一行包含一个正整数 $T \le 100$，表示测试用例的数量。

接下来的 $T$ 行，每行包含一个长度为 $1 \le L \le 100$ 的字符串，完全由集合 $\{2, 4, 8\}$ 中的数字字符组成（这是我们对给定列表的表示方式）。

输出格式

对于每个测试用例，输出一行，表示通过在输入列表中插入零个或多个来自集合 $\{2, 4, 8\}$ 的数字所能构建的最短的美妙列表。如果有多个最优解，输出字典序最小的一个。

样例

输入样例 1

3
222
8224
42424

输出样例 1

2222
8224
422422448