Задано рядок \textbf{s}. Назвемо циклічним зсувом \textbf{s} на \textbf{k} (\textbf{0} ≤ \textbf{k} < \textbf{|s|}) рядок, отриманий видаленням \textbf{k} символів з початку \textbf{s} і дописуванням їх у кінець у тому ж порядку. Необхідно знайти таке \textbf{k}, що циклічний зсув \textbf{s} на \textbf{k} лексикографічно мінімальний. Якщо таких \textbf{k д}екілька, то необхідно знайти серед усіх таких \textbf{k} мінімальне. \InputFile У першому рядку записано одне число - кількість тестів \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{20}). Далі записано \textbf{m} рядків, які складаються з символів з кодами від \textbf{33} до \textbf{126}. Гарантується, що розмір вхідного файлу не перевищуєт \textbf{90} кілобайт. \OutputFile Для кожного рядка виведіть шукане \textbf{k}.