Иногда программисты очень странно прячут свои пароли. Посмотрим, например, как Билли "Хакер" Гейтс прячет свой пароль. Билли выбирает строку \textbf{s} состоящую из латинских букв длины \textbf{l}. Затем он совершает все \textbf{l-1 }однобуквенных циклических сдвигов влево и в качестве пароля выбирает префикс лексикографически наименьшей из образованных строк (включая\textbf{ s}). Например, рассмотрим строку \textbf{alabala}. Циклические однобуквенные левые сдвиги (включая начальную строку) имеют вид: \textbf{alabala} \textbf{labalaa} \textbf{abalaal} \textbf{balaala} \textbf{alaalab} \textbf{laalaba} \textbf{aalabal} и лексикографически первой из них является строка \textbf{aalabal}. Первая буква этой строки находится в позиции \textbf{6} начальной строки (позиции в строках нумеруются с \textbf{0}). Напишите программу, которая по заданной строке \textbf{s} найдет начальную позицию лексикографически наименьшего левого циклического сдвига. Если лексикографически наименьший сдвиг встречается более одного раза, следует вывести наименьшую из таких позиций. \InputFile Первая строка содержит количество тестов \textbf{t}. Первая строка каждого теста содержит длину \textbf{l} (\textbf{5 }≤ \textbf{l }≤ \textbf{100000}) входной строки, а вторая - саму строку \textbf{s}. \OutputFile Вывести в точности \textbf{t} строк, по одной на каждый тест. В каждой строке следует вывести искомую начальную позицию.