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