시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 247 176 159 76.442%

문제

환규와 태욱이는 둘이서 즐길 수 있는 간단한 게임인 탕수육 게임을 하기로 했다. 게임의 규칙은 다음과 같다.

  1. 누가 먼저 시작할지 순서를 정한다.
  2. 먼저 시작하는 사람이 단어의 가장 첫 글자를 말한다.
  3. 이후 두 사람이 번갈아 가며 자신의 차례에 이전 사람이 말한 글자의 다음 글자를 말한다.
  4. 만약 이전 사람이 단어의 가장 마지막 글자를 말했다면 자신의 차례에 단어의 가장 첫 글자를 말한다.
  5. 만약 자신의 차례에 잘못된 글자를 말하면 게임에서 지게 된다.

위 규칙을 이용해 탕수육이란 단어를 가지고 게임을 진행하면 다음과 같다.

육 …

위 예시에서 밑줄 친 부분은 첫 번째 사람이, 밑줄이 없는 부분은 두 번째 사람이 말하게 되는 부분이다. 이 때 밑줄 그어진 부분만 따로 살펴보면 “탕육수탕육수…”가 됨을 알 수 있는데, 따라서 먼저 시작하는 사람은 게임을 시작하기 전에 “탕육수” 만을 기억한 후 상대방이 어떤 단어를 말하든 “탕육수” 순서로 계속 반복해서 말하면 절대로 틀리지 않는다. 만약 “탕육”이나 “탕육수탕”을 기억한다면 기억한 문자열을 처음부터 하나씩 순서대로 말했을 때 자신의 차례에 올바르지 않은 문자를 말하게 되어 게임에서 지게 된다. “탕육수탕육수”를 기억한다고 하더라도 자신의 차례에 틀린 문자를 말하게 되지는 않지만, “탕육수” 만을 기억해도 게임을 진행할 수 있으므로 이 경우 항상 기억해야 할 최소한의 글자만을 기억한다고 가정한다. 또한, 나중에 시작하는 사람도 게임을 시작하기 전에 “수탕육”만을 기억한 다음 “수탕육” 순서대로 반복해서 말하면 절대로 틀리지 않는다.

환규와 태욱이는 이번에는 한글 대신 알파벳을 사용해서 게임을 해보기로 했다. 만약 주어진 단어가 “ABC”이고, 환규가 먼저 시작한다면 환규는 “ACB”를, 태욱이는 “BAC” 만을 기억하면 게임을 지지 않게 된다. 게임에 사용할 알파벳으로 된 문자열이 주어질 때, 두 사람이 미리 기억하고 있어야 되는 문자열 중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 게임에 사용할 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고 26보다 작거나 같다. 게임에 사용할 문자열은 알파벳 대문자로만 이루어져 있으며 같은 알파벳을 두 개 이상 포함하지 않는다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫 번째 줄에 먼저 시작한 사람이 기억해야 될 문자열 중 가장 짧은 것을 알파벳 대문자로 출력한다. 두 번째 줄에는 나중에 시작한 사람이 기억해야 될 문자열중 가장 짧은 것을 알파벳 대문자로 출력한다.

예제 입력

4
ABC
ABCFXZ
K
DY

예제 출력

ACB
BAC
ACX
BFZ
K
K
D
Y

힌트