The Last Word (Large)

게임 쇼 The Last Word에서 진행자는 영어 대문자로 이루어진 문자열 $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$를 보여 주었다. 어떤 마지막 단어를 만들어야 이기는지 구하시오.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 문자열 $S$ 하나로 이루어진 한 줄이다.

제한

• $1 \le T \le 100$
• $1 \le$ ($S$의 길이) $\le 1000$
• $S$는 영어 대문자로만 이루어져 있다.

각 테스트 케이스마다 Case #x: y 형식의 줄을 하나 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 문제에서 설명한 이기는 마지막 단어이다.