C1066 - 环状序列
题目描述
一些DNA序列以环形存在，如下图所示，展示了一个环形序列“CGAGTCAGCT”，即“CGAGTCAGCT”中的最后一个符号“T”与第一个符号“C”相连。我们总是顺时针方向读取环形序列。
由于直接在计算机中存储环形序列并不容易，我们决定将其存储为线性序列。然而，通过切割环形序列的任何位置，可以从一个环形序列获得多个线性序列。
因此，我们还决定存储在从环形序列获得的所有线性序列中字典序最小的线性序列。
你的任务是从给定的环形序列中找到字典序最小的序列，以图中的例子为例，字典序最小的序列是“AGCTCGAGTC”。
如果有两个或更多的线性序列在字典序上是最小的，你只需要找出其中任意一个（实际上，它们是相同的）。
输入格式
第1行，一个正整数T，代表接下来有T组测试数据
接下来有T行，每行一个字符串，代表一个环形序列，该序列以任意线性序列的形式呈现，该字符串中只包含A、C、G、T这4个字符（可以只包含其中一部分）
输出格式
输出T行，每行对应包含测试用例中字典序最小的字符串序列。
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 2 CGAGTCAGCT CTCC |
AGCTCGAGTC CCCT |
数据范围与提示
100%的数据：$1 \le T \le 10$，2 <= 每个字符串长度 <= 100
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1066.in，输出文件名为：C1066.out