매우 더러운 사슬

자전거 사슬은 여러 개의 고리가 하나의 고리 모양(원형)으로 연결되어 있습니다. 각 고리의 한쪽 면에는 영어 소문자가 하나씩 적혀 있습니다.

이 사슬을 떼어 내려면 고리 사이의 이음매 한 곳을 끊어야 합니다. 어떤 이음매를 끊으면 원형이던 사슬이 한 줄로 펴지고, 끊은 지점 바로 다음 고리부터 순서대로 글자를 읽으면 하나의 단어가 만들어집니다. 즉 어느 이음매를 끊느냐에 따라 만들어지는 단어는 사슬에 적힌 글자열의 서로 다른 회전(rotation)들이 됩니다.

이렇게 만들 수 있는 단어들 가운데 사전순으로 가장 작은 단어를 구하세요.

사슬을 뒤집어서 반대 방향으로 읽는 것은 허용되지 않습니다. 글자를 읽는 방향은 한 방향으로 고정됩니다.

첫째 줄에 테스트의 개수를 나타내는 자연수 $d$ ($1 \le d \le 100$)가 주어집니다.

다음 $d$개의 줄에 각 테스트가 한 줄씩 주어집니다. 각 줄은 사슬의 고리에 적힌 글자를 순서대로 나열한, 영어 소문자로만 이루어진 문자열입니다. 사슬의 고리 수(문자열의 길이)는 최소 $1$개, 최대 $1\,000\,000$개입니다.

각 테스트마다, 그 사슬을 끊어서 만들 수 있는 사전순으로 가장 작은 단어를 한 줄에 하나씩 출력합니다.