Smallest Lexicographical Rotation

Given a string s, a rotation of s is defined as moving some number of characters from the beginning of the string to its end while preserving their order. Formally, for an index \( i \) (0 \( \leq i < n \), where \( n \) is the length of the string), the rotation is defined as:

\[ s[i:] + s[:i] \]

Your task is to determine the smallest lexicographical rotation of the given string. That is, among all rotations of s, you must output the one that is smallest when compared using standard lexicographical order.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

T
s1
s2
...
sT

Here, T is an integer representing the number of test cases. Each of the following T lines contains a non-empty string for which you need to compute the smallest lexicographical rotation.

outputFormat

For each test case, output the smallest lexicographical rotation of the given string. Each answer should be printed on a separate line to standard output (stdout).

## sample

3
cba
apple
aaba

acb
apple
aaab

</p>