Circular Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Find the lexicographically smallest rotation of each given circular DNA string.

Level: Easy3 of 10
Topics: String, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
2
CGAGTCAGCT
CTCC
```
Expected output
```
AGCTCGAGTC
CCCT
```
Example 2
Input
```
1
TA
```
Expected output
```
AT
```