Problem1085--环状序列

1085: 环状序列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 607  Solved: 409
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个长度为n的环状序列,长度为n的环状串有n种表示方法,分别为从某个位置开始顺时针得到,在这些排列中字典顺序最小的称“最小表示”。
如CTCC的最小表示为CCCT,CGAGTCAGCT的最小表示为AGCTCGAGTC。

环状序列如下图所示: 

Input

输入第一行包括一个正整数T,代表测试用例数目。
接下来的T行每一行包含一个环状序列s ,s的长度小于1000.

Output

对于每一个环状序列s,输出其最小表示。

Sample Input

2
CGAGTCAGCT
CTCC

Sample Output

AGCTCGAGTC
CCCT

HINT

Source/Category