Іноді програмісти дуже дивно ховають свої паролі. Подивимлсь, наприклад, як Біллі "Хакер" Гейтс ховає свій пароль. Біллі вибирає рядок \textbf{S}, який складається з латинських букв довжини \textbf{L}. Потім він здійснює усі \textbf{L-1 }однобуквенних циклічних зсувів ліворуч і у якості пароля вибирає префікс лексикографічно найменшої з утворених рядків (включаючи\textbf{ S}). Наприклад, розглянемо рядок \textbf{alabala}. Циклічні однобуквені ліві зсуви (включаючи початковий рядок) мають вигляд: \textbf{alabala} \textbf{labalaa} 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} рядків, по одному для кожного тесту. У кожному рядку потрібно вивести шукану початкову позицію.