Circular Sequence

Some DNA sequences exist in circular form. The figure below shows the circular sequence CGAGTCAGCT: the last symbol T connects back to the first symbol C. A circular sequence is always read clockwise.

A circular sequence is awkward to store directly, so we store it as a linear sequence instead. Cutting the circle at any position yields a different linear sequence, so a circular sequence of length $n$ has $n$ possible linear forms. Among them we keep the one that is lexicographically smallest.

Given a circular sequence, output its lexicographically smallest linear form. For the sequence in the figure the answer is AGCTCGAGTC. Two different cut positions can tie for smallest only when they produce the exact same string, so this smallest linear form is unique.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one circular sequence, written as an arbitrary linear form. Because these are DNA sequences, every symbol is one of A, C, G, or T. Each sequence has length between $2$ and $100$ inclusive.

For each test case, print one line containing the lexicographically smallest linear form of its circular sequence.