원형 서열

어떤 DNA 서열은 원형으로 존재한다. 아래 그림은 원형 서열 CGAGTCAGCT를 나타내며, 마지막 기호 T가 첫 기호 C로 다시 이어진다. 원형 서열은 항상 시계 방향으로 읽는다.

원형 서열을 그대로 저장하기는 번거로우므로 선형 서열로 바꾸어 저장한다. 원을 어느 위치에서 자르느냐에 따라 서로 다른 선형 서열이 나오므로, 길이가 $n$인 원형 서열에서는 $n$가지의 선형 서열을 얻을 수 있다. 이 중에서 사전순으로 가장 앞서는 것 하나를 저장한다.

원형 서열이 주어지면 사전순으로 가장 앞서는 선형 서열을 출력하여라. 그림의 예시에서 정답은 AGCTCGAGTC이다. 서로 다른 절단 위치가 사전순 최소로 겹치는 경우는 완전히 같은 문자열을 만들 때뿐이므로, 이 최소 선형 서열은 유일하다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 임의의 선형 형태로 적힌 원형 서열이 하나씩 주어진다. DNA 서열이므로 각 기호는 A, C, G, T 중 하나이다. 각 서열의 길이는 $2$ 이상 $100$ 이하이다.

각 테스트 케이스마다 해당 원형 서열의 사전순으로 가장 앞서는 선형 서열을 한 줄에 출력한다.