Cyclic Shifts#5302
Given a string , define a cyclic shift of by (0 \leq k < |s|) as the string obtained by removing the first characters from and appending them, in order, to the end of the string.
Your task is to find the value of such that the cyclic shift of by produces the lexicographically smallest string possible. If there are multiple such , select the smallest.
The first line contains a single integer (1 \leq m \leq 20), the number of test cases. Each of the following lines contains a string consisting of characters with ASCII codes from to inclusive. The total size of the input file does not exceed kilobytes.
For each string, output the minimal resulting in the lexicographically smallest cyclic shift.
Example 1