eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Циклические сдвиги

Циклические сдвиги

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Дана строка s. Назовем циклическим сдвигом s на k (0k < |s|) строку, полученную удалением k символов из начала s и дописыванием их в конец в том же порядке.

Необходимо найти такое k, что циклический сдвиг s на k лексикографически минимальный. Если таких k несколько, то необходимо найти среди всех таких k минимальное.

Входные данные

В первой строке записано одно число - количество тестов m (1m20). Далее записаны m строк, состоящих из символов с кодами от 33 до 126. Гарантируется, что размер входного файла не превосходит 90 килобайт.

Выходные данные

Для каждой строке выведите искомое k.

Пример

Входные данные #1
2
kitten
hedgehog
Выходные данные #1
4
2