마지막 단어

게임 쇼 「마지막 단어」에서 진행자는 참가자에게 대문자 영어 문자로 이루어진 문자열 S를 보여 주며 한 라운드를 시작한다. 참가자에게는 처음에 아무것도 적혀 있지 않은 화이트보드가 있다. 그러고 나서 진행자는 S의 문자들을 S에 나타나는 순서대로 하나씩 참가자에게 제시한다. 진행자가 첫 문자를 제시하면 참가자는 그것을 화이트보드에 적는다. 이는 길이가 문자 하나에 불과하더라도 게임의 첫 단어로 간주된다. 그 후 진행자가 문자를 제시할 때마다 참가자는 진행자가 다음 문자로 넘어가기 전에 그 문자를 화이트보드에 적힌 단어의 맨 앞이나 맨 뒤에 적어야 한다. 더 제시할 문자가 없다면 진행자는 게임을 끝낸다.

예를 들어 S = CAB일 때, 화이트보드에 C이라는 단어를 적은 뒤 참가자는 다음 네 가지 선택 조합 중 하나를 택할 수 있다:

• A를 C 앞에 놓아 AC을 만든 다음, B를 AC 앞에 놓아 BAC을 만든다

• A를 C 앞에 놓아 AC을 만든 다음, B를 AC 뒤에 놓아 ACB을 만든다

• A를 C 뒤에 놓아 CA을 만든 다음, B를 CA 앞에 놓아 BCA을 만든다

• A를 C 뒤에 놓아 CA을 만든 다음, B를 CA 뒤에 놓아 CAB을 만든다

주어진 규칙에 따라 참가자가 S의 모든 문자를 다 적었을 때 완성된 단어를 마지막 단어라고 한다. 만들어질 수 있는 모든 마지막 단어를 알파벳순으로 정렬한 목록에서 참가자의 마지막 단어가 맨 마지막이라면 참가자가 게임에서 승리한다. 위 예제에서 승리하는 마지막 단어는 CAB이며, 이는 원래 단어와 우연히 같다. S = JAM인 게임에서 승리하는 마지막 단어는 MJA이다.

이 쇼의 다음 참가자는 당신이며, 진행자는 방금 문자열 S를 보여 주었다. 승리하려면 어떤 마지막 단어를 만들어야 하는가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ S의 길이 ≤ 15.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ S의 길이 ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 문자열 S가 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 문제 설명과 같이 승리하는 마지막 단어이다.