소문자 영어 알파벳으로 이루어진 문자열 $S$와 처음에 비어 있는 문자열 $T$가 주어집니다.

$S$가 빈 문자열이 될 때까지 여러 번의 연산을 해야 합니다. 매번 다음 세 가지 연산 중 하나를 할 수 있습니다:

• $S$의 첫 번째 문자를 삭제하고 $T$의 끝에 붙입니다.
• $S$의 마지막 문자를 삭제하고 $T$의 끝에 붙입니다.
• $S=ABA^R$를 만족하는 비어 있지 않은 문자열 $A,B$를 골라 $S=B$로 바꾸고 문자열 $A$를 $T$의 끝에 붙입니다.

여기서 $A^R$은 문자열 $A$를 뒤집은 문자열입니다.

모든 연산 계획 중에서 얻을 수 있는 사전순으로 가장 작은 $T$를 구하세요.

입력

이 문제에는 여러 테스트 케이스가 있습니다.

첫 번째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 $t$ ($1\le t\le 10^5$)가 주어집니다.

각 테스트 케이스에 대해:

한 줄에 소문자로 이루어진 문자열 $S$ ($1\le |S|\le 5\times 10^5$)가 주어집니다.

모든 테스트 케이스의 $|S|$의 합은 $5\times 10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 답을 나타내는 문자열을 한 줄에 출력하세요.

예제

입력 1

6
cba
zayaz
aaaaa
xazbx
ababa
aa

출력 1

abc
zaay
aaa
xabz
aaba
aa