Циклічні зсуви

Задано рядок s. Назвемо циклічним зсувом s на k (0 ≤ k < |s|) рядок, отриманий видаленням k символів з початку s і дописуванням їх у кінець у тому ж порядку.

Необхідно знайти таке k, що циклічний зсув s на k лексикографічно мінімальний. Якщо таких k декілька, то необхідно знайти серед усіх таких k мінімальне.

Вхідні дані

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

Вихідні дані

Для кожного рядка виведіть шукане k.

Приклади