Жила-була відома акторка. Як ви вже здогадались, більше усього вона вона віддавала перевагу грати античні комедії. Усі люди любили її. Проте вона не була зацікавлена у натовпі. Її найбільшим хоббі були бусинки довільного виду. Багато виробників бус працювали на неї, виготавляючи нові намиста та браслети кожен день. Одного разу вона подзвонила своєму головному інспектору бісера і повідомила, що хоче придбати дуже довге і спеціальне намисто. Намисто повинно бути виготовлено зі скляних бусинок різного розміру, з'єднаних одна з одною. Проте ніяка нитка не повинна проходити крізь бусинки - у довільний момент часи повинна бути наявною можливість від'єднати довільну бусинку. Актриса вибрала послідовність бусинок і хоче зробити з них намисто. Проте потім зрозуміла проблему. З'єднання між двома сусідніми бусинками не дуже надійне, тому намисто може розірватись під дією власної ваги. Ситуація стає ще гіршою, якщо намисто розпадеться на частини. Точки з'єднання бусинок є дуже важливими. Якщо маленькі бусинки знаходяться на початку, то можливість розриву намиста набагато більша, ніж тоді, якби там були великі бусинки. Виробник бус хоче перевірити надійність намиста і вимагає програму, яка зможе визначити точку найбільш можливого розриву. Намисто задається рядком \textbf{A = a_1a_2 ... a_m}, який описує розміри бусинок. Нfмисто замкнуте, тому після бусинки \textbf{a_m} йде бусинка \textbf{a_1}. Точка з'єднання \textbf{i} вважається гіршою точки \textbf{j} тоді і лише тоді, коли рядок \textbf{A\[i\]} = \textbf{a_ia_\{i+1\}...a_na_1...a_\{i-1\}} лексикографічно менший рядка \textbf{A\[j\]} = \textbf{a_ja_\{j+1\}... a_na_1...a_\{j-1\}}. Рядок \textbf{a_1a_2...a_n} лексикографічно менший рядка \textbf{b_1b_2...b_n} якщо існує таке ціле \textbf{i} (\textbf{i} ≤ \textbf{n}), що \textbf{a_j = b_j} для кожного \textbf{j} (\textbf{1} ≤ \textbf{j} < \textbf{i} та \textbf{a_i} < \textbf{b_i}). \InputFile Перший рядок містить кількість тестів \textbf{N}. Кожен тест задається одним рядком, який описує структуру намиста. Максимальна довжина намиста \textbf{10000} символів. Кожна бусинка задається символом нижнього регістру латинського алфавіту (\textbf{a}-\textbf{z}), де \textbf{a} < \textbf{b}...\textbf{z}. \OutputFile Для кожного тесту у окремому рядку вивести одне ціле число - номер бусинки, яка розірветься першою, тобто таке \textbf{i}, що рядок \textbf{A\[i\]} є лексикографічно найменшим серед усіх \textbf{n} можливих роз'єднань намиста. Якщо задача має декілька розв'язків, то слідт вивести той, у якому значення \textbf{i} найменше.