{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"\n1\nSome DNA sequences exist in circular forms as inthe following gure, which shows a circular sequence\\CGAGTCAGCT\", that is, the last symbol \\T\" in\\CGAGTCAGCT\" is connected to the rst symbol \\C\". We al-ways read a circular sequence in the clockwise direction.Since it is not easy to store a circular sequence in a com-puter as it is, we decided to store it as a linear sequence.However, there can be many linear sequences that are ob-tained from a circular sequence by cutting any place of thecircular sequence. Hence, we also decided to store the linearsequence that is lexicographically smallest among all linearsequences that can be obtained from a circular sequence.Your task is to nd the lexicographically smallest sequencefrom a given circular sequence. For the example in the gure,the lexicographically smallest sequence is \\AGCTCGAGTC\". If there are two or more linear sequences thatare lexicographically smallest, you are to nd any one of them (in fact, they are the same).InputThe input consists ofTtest cases. The number of test casesTis given on the rst line of the input le. Each test case takes one line containing a circular sequence that is written as an arbitrary linearsequence. Since the circular sequences are DNA sequences, only four symbols, `A\u0027, `C\u0027, `G\u0027 and `T\u0027, areallowed. Each sequence has length at least 2 and at most 100.OutputPrint exactly one line for each test case. The line is to contain the lexicographically smallest sequencefor the test case.\n\nSample Input\n\n2\n\nCGAGTCAGCT\n\nCTCC\n\nSample Output\n\nAGCTCGAGTC\n\nCCCT\n\n"}}]}