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

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

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

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

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

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

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

Примеры