eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

Input data

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

Output data

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

Examples

Input example #1
2
kitten
hedgehog
Output example #1
4
2