Дана строка \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}.