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