좋은 수열

2048 게임의 1차원 판을 생각한다.

각 원소가 2의 거듭제곱인 수열이 있다. 이 수열을 오른쪽으로 밀면 수열이 압축된다. 값이 같은 두 원소가 이웃해 있으면 두 원소는 합으로 합쳐진다. 한 번 미는 동안 각 원소는 최대 한 번만 합쳐지고, 밀기는 오른쪽 끝에서부터 처리하므로 양쪽 이웃과 모두 합칠 수 있는 원소는 오른쪽 이웃과 합쳐진다.

한 번의 밀기는 이렇게 진행한다. 아직 처리하지 않은 원소 중 가장 오른쪽 원소를 본다. 바로 왼쪽 원소의 값이 그 원소와 같으면 두 원소를 합으로 바꾸고 둘 다 처리한 것으로 표시한다. 값이 다르면 그 원소는 그대로 남는다. 그다음 아직 처리하지 않은 원소로 왼쪽으로 옮겨 가면서 수열의 맨 앞까지 반복한다.

예를 들어 [2, 2, 2, 2]는 한 번 밀면 [4, 4]가 되고, [2, 2, 2]는 [2, 4]가 되어 더 밀어도 바뀌지 않는다. 여러 번 밀면 원소가 하나만 남는 수열도 있다. [8, 2, 2, 4]는 [8, 4, 4], [8, 8], [16] 순서로 줄어든다.

밀기만 반복해서 원소가 하나인 수열로 줄일 수 있으면 그 수열을 좋은 수열이라고 한다.

원소가 모두 2, 4, 8 중 하나인 수열이 주어진다. 이 수열의 아무 위치에나 2, 4, 8 중에서 고른 원소를 0개 이상 끼워 넣어 좋은 수열을 만든다. 주어진 수열의 원소는 원래 순서를 그대로 지켜야 한다. 이렇게 만들 수 있는 가장 짧은 좋은 수열을 구한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $1 \le T \le 100$이다.

다음 $T$개의 줄에 각각 길이가 $L$인 문자열이 하나씩 주어진다. $1 \le L \le 100$이고, 문자열은 숫자 2, 4, 8로만 이루어진다. 이 문자열이 주어진 수열이다.

각 테스트 케이스마다 한 줄에, 주어진 수열에 2, 4, 8을 끼워 넣어 만들 수 있는 가장 짧은 좋은 수열을 출력한다. 입력과 같은 형식으로 숫자를 이어 붙여 출력한다. 가장 짧은 수열이 여러 개면 사전순으로 가장 앞서는 것을 출력한다.