The smallest cyclic shift

A cyclic shift of a string is created by moving some of the initial characters to the end of the string. Your task is to determine the lexicographically smallest cyclic shift for a given string.

Input

The first line of the input contains the integer k, representing the number of test cases. The next k lines each contain a string. Each string is composed of characters with ASCII codes ranging from 33 to 126. The total size of the input will not exceed one megabyte.

Output

For each test case, output a single line containing the smallest cyclic shift.

Examples