Nice Numbers

Image from wikipedia commons cc by-sa 3.0

Either way, we will define our own one-dimensional version of the game:

You are given a list of numbers containing only powers of $2$. You can “compress” this list by “pushing” it to the right. If two identical numbers are next to each other, push will cause them to merge. The “merge” in this context means that the two numbers are replaced by their sum. Each number can be merged only once—if they can merge with either of their neighbors, they merge with the one to the right. This process is evaluated from the right. For example, the list $[2, 2, 2, 2]$ will become $[4,4]$ after one push. For another example, given a list $[2,2,2]$, after a push, we end up with a new list $[2, 4]$ and we cannot change it further by “pushing”.

Now, some of these lists, after some number of pushes, may end up with a single element. Using the example: $[8, 2, 2, 4] \Rightarrow [8, 4, 4] \Rightarrow [8, 8] \Rightarrow [16]$.

If the list can be reduced to a single element list only by
“pushing”, we call such a list **nice**.

Your task is to take a given list and make it **nice** by adding some (maybe zero) elements from
$\{ 2, 4, 8\} $. To make
this problem a bit easier, the initial list can contain only
numbers in the set $\{ 2, 4, 8\}
$.

The first line of input contains a single positive integer $T \leq 100$ indicating the number of test cases. Next $T$ lines each contains a string of length $1 \leq L \leq 100$, composed entirely of digits from the set $\{ 2, 4, 8\} $ (our representation of the given list).

For each test case, output a line containing the shortest
**nice** list built out of the input list
by inserting zero or more of digits from the set $\{ 2, 4, 8\} $. If there are multiple
optimal solutions, output the lexicographically smallest
one.

Sample Input 1 | Sample Output 1 |
---|---|

3 222 8224 42424 |
2222 8224 422422448 |