Nice Numbers

Consider a one dimensional version of the game 2048.

You have a list whose entries are powers of two. Pushing the list to the right compresses it. Two neighbouring entries that hold the same value are replaced by their sum. Each entry merges at most once per push, and a push is processed from the right end, so an entry that could merge with either neighbour merges with the one on its right.

One push works like this. Look at the rightmost entry that has not been handled yet. If the entry immediately to its left holds the same value, replace the two by their sum and mark both as handled. If the values differ, the entry stays as it is. Then move left to the next entry that has not been handled and repeat until the front of the list is reached.

For example, [2, 2, 2, 2] becomes [4, 4] after one push, and [2, 2, 2] becomes [2, 4], which no further push changes. Some lists shrink to a single entry after several pushes: [8, 2, 2, 4] becomes [8, 4, 4], then [8, 8], then [16].

A list is nice if repeated pushes reduce it to a list with one entry.

You are given a list whose entries all come from the set 2, 4, 8. Insert zero or more entries chosen from 2, 4, 8 at any positions of the list so that the result is nice. The entries of the given list must keep their original order. Find the shortest nice list you can build this way.

The first line contains the number of test cases $T$, where $1 \le T \le 100$.

Each of the next $T$ lines contains one string of length $L$, where $1 \le L \le 100$. The string consists of the digits 2, 4 and 8 only, and it is the given list.

For each test case, print on one line the shortest nice list that can be built from the given list by inserting digits from 2, 4, 8. Print the list as a run of digits, in the same format as the input. If several shortest lists exist, print the lexicographically smallest one.