Smallest Lexicographical Rotation

Given a string \(S\) of length \(n\), a rotation is defined as a string obtained by moving a prefix of \(S\) to its end. Formally, if \(S = s_1s_2\ldots s_n\), then its \(i\)-th rotation is:

\(S_i = s_i s_{i+1} \ldots s_n s_1 \ldots s_{i-1}\)

Your task is to determine the smallest lexicographical rotation among all \(n\) possible rotations of \(S\). You will be given \(T\) test cases, and for each test case, you need to output the smallest rotation.

Note that the lexicographical order is the usual dictionary order.

inputFormat

The input is given from standard input (stdin) and has the following format:

• The first line contains an integer \(T\) denoting the number of test cases.
• Each of the following \(T\) lines contains a non-empty string \(S\).

outputFormat

For each test case, output a single line containing the smallest lexicographical rotation of the given string.

## sample

3
bca
abc
cab

abc
abc
abc

</p>