두 번 또는 한 번

대문자 알파벳으로 이루어진 문자열이 주어진다. 글자 중 원하는 만큼(전부여도 되고, 하나도 고르지 않아도 된다) 골라서 강조할 수 있다. 강조하는 글자들은 서로 연속일 필요가 없다. 그다음 문자열을 왼쪽에서 오른쪽으로 처리해서 새 문자열을 만든다. 강조하지 않은 글자는 한 번, 강조한 글자는 두 번 붙는다.

예를 들어 초기 문자열이 HELLOWORLD이면 H, 첫 번째와 마지막 L, 마지막 O를 강조해서 HHELLLOWOORLLD를 얻는다. 아무것도 강조하지 않으면 HELLOWORLD가 되고, 모든 글자를 강조하면 HHEELLLLOOWWOORRLLDD가 된다. 같은 글자라도 각 출현을 따로따로 강조할 수 있다.

강조 방법에 따라 여러 문자열이 나올 수 있다. 그중 사전 순으로 가장 앞에 오는 문자열을 출력한다. 문자열 $s$가 다른 문자열 $t$보다 앞에 오는 경우는, $s$가 $t$의 접두사이거나, 처음으로 달라지는 위치에서 $s$의 글자가 $t$의 글자보다 알파벳에서 앞설 때이다. 예를 들어 CODE, HELLO, HI, HIM, HOME, JAM은 이 순서로 정렬되어 있다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 문자열 $S$가 한 줄씩 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $S$로부터 만들 수 있는 문자열 중 사전 순으로 가장 앞선 문자열이다.

• $1 \le T \le 100$.
• $S$의 각 글자는 영어 대문자이다.

샘플 케이스 1에서 얻을 수 있는 문자열을 사전 순으로 모두 나열하면 PEEEEL, PEEEELL, PEEEL, PEEELL, PEEL, PEELL, PPEEEEL, PPEEEELL, PPEEEL, PPEEELL, PPEEL, PPEELL이다.

샘플 케이스 2에서 얻을 수 있는 문자열은 모두 A로만 이루어져 있다. 그중 가장 짧은 문자열이 나머지 문자열의 접두사이므로 사전 순으로 가장 앞선다.

샘플 케이스 3에서 CODEJAMDAY로 만들 수 있는 문자열은 $1024$개이고, 그중 사전 순으로 가장 작은 것은 CCODDEEJAAMDAAY이다.