T792598 【C1066】 - 环状序列

一些DNA序列以环形存在，如下图所示，展示了一个环形序列“CGAGTCAGCT”，即“CGAGTCAGCT”中的最后一个符号“T”与第一个符号“C”相连。我们总是顺时针方向读取环形序列。  由于直接在计算机中存储环形序列并不容易，我们决定将其存储为线性序列。然而，通过切割环形序列的任何位置，可以从一个环形序列获得多个线性序列。 因此，我们还决定存储在从环形序列获得的所有线性序列中字典序最小的线性序列。 你的任务是从给定的环形序列中找到字典序最小的序列，以图中的例子为例，字典序最小的序列是“AGCTCGAGTC”。 如果有两个或更多的线性序列在字典序上是最小的，你只需要找出其中任意一个（实际上，它们是相同的）。

第1行，一个正整数T，代表接下来有T组测试数据 接下来有T行，每行一个字符串，代表一个环形序列，该序列以任意线性序列的形式呈现，该字符串中只包含`A`、`C`、`G`、`T`这4个字符（可以只包含其中一部分）

输出T行，每行对应包含测试用例中字典序最小的字符串序列。

100%的数据：$1 \le T \le 10$，2