Cyclic Shifts

Given a string (s), a cyclic shift of (s) by (k) ((0 $\le$ k < |s|)) is defined as the string formed by removing (k) characters from the start of (s) and appending them to the end in the same sequence.

Your task is to determine the value of (k) such that the cyclic shift of (s) by (k) results in the lexicographically smallest string. If there are multiple values of (k) that achieve this, choose the smallest (k).

Input

The first line contains a single integer, (m) ((1 $\le$ m $\le$ 20)), representing the number of test cases. Each of the following (m) lines contains a string composed of characters with ASCII codes ranging from 33 to 126. The total size of the input file will not exceed 90 kilobytes.

Output

For each string, output the smallest (k) that results in the lexicographically minimal cyclic shift.

Examples