0065. Circular Shifts

Имя входного файла:	shifts.in
Имя выходного файла:	shifts.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Consider the following operation applied to the string S consisting of L characters: remove first K (0 ≤ K < L) characters from the string and add them to its end. Let us call the result of this operation the {\em circular shift} of S by K.

For each given string S find such K that the circular shift of S by K is lexicographically smallest among all circular shifts of S.

Input file

The first line of the input file contains one integer number (1≤ M≤ 20) – the number of test cases.

Each of the following M lines contains the string to be processed. The strings contain only characters with ASCII codes from 33 to 126. Alphabetic characters are treated case sensitive. It is guaranteed that the input file size does not exceed 90000.

Output file

Output M numbers – for each given string S output such K that the circular shift of S by K is lexicographically smallest. If there are several such K output the smallest one.

Examples:

shifts.in	shifts.out
2 kitten hedgehog	42

Источник: Petrozavodsk Winter 2003. St. Petersburg Contest I

Обсудить       Отправить решение