Description

长度为n的环状串有n种表示法，分别为从某个位置开始顺时针得到。例如，图3-4的环状串有10种表示：CGAGTCAGCT，GAGTCAGCTC，AGTCAGCTCG等。在这些表示法中，字典序最小的称为"最小表示"。 输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。

Format

Input

输入t+1行，第1行输入需要处理字符串的个数，接下来t行输入环状串，每行长度不超过100。

Output

输出t行，环状串的最小表示。

Samples

2
CTCC
CGAGTCAGCT

CCCT
AGCTCGAGTC