두 배 또는 하나

영어 대문자로 이루어진 문자열이 주어진다. 문자 중 원하는 개수만큼 강조 표시할 수 있다(모두 강조하거나 하나도 강조하지 않을 수도 있다). 강조 표시한 문자들은 연속할 필요가 없다. 그런 다음 문자들을 왼쪽에서 오른쪽으로 처리하여 새 문자열을 만든다. 강조 표시하지 않은 문자는 새 문자열에 한 번 추가하고, 강조 표시한 문자는 두 번 추가한다.

예를 들어 초기 문자열이 HELLOWORLD이면, H, 첫 번째와 마지막 L, 그리고 마지막 O를 강조 표시하여 HELLOWORLD $\Rightarrow$ HHELLLOWOORLLD를 얻을 수 있다. 마찬가지로 아무것도 강조 표시하지 않으면 HELLOWORLD을 얻고, 모든 문자를 강조 표시하면 HHEELLLLOOWWOORRLLDD을 얻는다. 같은 문자가 여러 번 등장하더라도 각 등장은 독립적으로 강조 표시할 수 있음에 유의하라.

문자열이 주어졌을 때, 강조 표시 선택에 따라 이 과정의 결과로 얻을 수 있는 문자열이 여러 개 존재한다. 이 모든 문자열 중 알파벳순(사전순이라고도 한다)으로 가장 먼저 나오는 문자열을 출력한다.

참고: 문자열 $s$이 서로 다른 문자열 $t$보다 알파벳순으로 앞서는 것은 $s$이 $t$의 접두사이거나, $s$과 $t$이 처음으로 다른 위치에서 $s$의 문자가 $t$의 문자보다 알파벳에서 앞설 때이다. 예를 들어 다음 문자열들은 알파벳순으로 나열되어 있다: CODE, HELLO, HI, HIM, HOME, JAM.

제한

시간 제한: 2초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$의 각 문자는 영어 알파벳 대문자이다.

테스트 세트 1 (Visible Verdict)

$1 \le$ $\mathbf{S} \le 10$의 길이.

테스트 세트 2 (Hidden Verdict)

$1 \le$ $\mathbf{S} \le 100$의 길이.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 하나의 문자열 $\mathbf{S}$을 포함하는 한 줄로 설명된다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 위에서 설명한 과정을 통해 $\mathbf{S}$에서 만들 수 있는 문자열들의 집합 중 알파벳순으로 가장 먼저 나오는 문자열이다.

예제 케이스 #1에서 얻을 수 있는 모든 문자열을 알파벳순으로 나열하면 다음과 같다: PEEEEL, PEEEELL, PEEEL, PEEELL, PEEL, PEELL, PPEEEEL, PPEEEELL, PPEEEL, PPEEELL, PPEEL, 그리고 PPEELL.

예제 케이스 #2에서 얻을 수 있는 모든 문자열은 A만을 포함한다. 그중 가장 짧은 문자열은 다른 모든 문자열의 접두사이므로 알파벳순으로 가장 앞선다.

예제 케이스 #3에서 CODEJAMDAY로부터 생성할 수 있는 문자열은 $1024$개이며, 그중 사전순으로 가장 작은 문자열은 CCODDEEJAAMDAAY이다.