Схований пароль#5752
Іноді програмісти дуже дивно ховають свої паролі. Наприклад, розглянемо, як Біллі «Хакер» Гейтс ховає свій пароль. Біллі вибирає рядок зі строчних латинських літер довжини . Потім він робить усі l-1 можливих однобуквених циклічних зсувів рядка вліво і серед всіх отриманих рядків (включаючи ) вибирає лексикографічно найменший. Біллі використовує префікс цього рядка як пароль.
Наприклад, розглянемо рядок alabala. Однобуквені циклічні зсуви вліво (включаючи початковий рядок):
alabala labalaa abalaal balaala alaalab laalaba aalabal
Лексикографічно першим серед них є рядок aalabal. Перша літера цього рядка знаходиться на позиції в початковому рядку (позиції нумеруються з ).
Напишіть програму, яка для заданого рядка знаходить початкову позицію лексикографічно найменшого однобуквеного циклічного зсуву вліво. Якщо такий зсув зустрічається більше одного разу, виведіть найменшу з таких позицій.
Перший рядок містить ціле число — кількість тестів.
Кожен тест складається з двох рядків. Перший рядок містить число (5 \leq l \leq 100\,000), другий — рядок .
Виведіть рівно рядків. Для кожного тесту виведіть одну відповідь — шукану початкову позицію.
Приклад 1