Скляні бусинки#2912

Скляні бусинки

1 секунда

10 мегабайтів

Дуже легка

Жила-була відома актриса. Як і слід було очікувати, найбільше вона любила виступати в античних комедіях. Усі її обожнювали, але їй не були цікаві натовпи людей. Її найбільшим хобі було колекціонування намистин усіх видів. Для неї працювали багато майстрів, які щодня виготовляли нові намиста й браслети. Одного дня вона покликала свого головного Інспектора Майстрів Намистин (ІМН) і сказала йому, що хоче дуже довге й особливе намисто.

Намисто має бути зроблене зі скляних намистин різних розмірів, кожна з'єднана одна з одною, але без нитки, що проходить крізь намистини—так, щоб будь-яку намистину можна було від'єднати в будь-який момент. Актриса обрала послідовність намистин, яку вона хотіла, й ІМН пообіцяв зробити це намисто. Але виникла проблема: з'єднання між двома сусідніми намистинами не є дуже надійним, тож намисто може порватися під власною вагою. Ситуація ще гірша, якщо намисто розривається. Точки, де намистини з'єднані, дуже важливі. Якщо на початку знаходяться маленькі намистини, ймовірність розриву вища, ніж якщо б там були великі. Майстер хоче перевірити надійність намиста й потребує програму, яка визначить найгіршу можливу точку роз'єднання.

Намисто описується рядком $A = a_{1} a_{2} \dots a_{m}$ A = a_1 a_2 \ldots a_m, що задає розміри відповідних намистин; намисто є круговим, тобто після намистини $a_{m}$ a_m йде $a_{1}$ a_1.

З'єднання в позиції $i$ вважається гіршим за з'єднання в позиції $j$ тоді й лише тоді, якщо рядок $A [i] = a_{i} a_{i + 1} \dots a_{m} a_{1} \dots a_{i - 1}$ A[i] = a_i a_{i+1} \ldots a_m a_1 \ldots a_{i-1} є лексикографічно меншим, ніж рядок $A [j] = a_{j} a_{j + 1} \dots a_{m} a_{1} \dots a_{j - 1}$ A[j] = a_j a_{j+1} \ldots a_m a_1 \ldots a_{j-1}. Рядок $a_{1} a_{2} \dots a_{n}$ a_1 a_2 \ldots a_n є лексикографічно меншим за рядок $b_{1} b_{2} \dots b_{n}$ b_1 b_2 \ldots b_n, якщо існує такий індекс $i$ $(i \leq n)$ (i \leq n), що $a_{j} = b_{j}$ a_j = b_j для всіх $j$ $(1 \leq j < i)$ (1 \leq j < i), і $a_{i} < b_{i}$ a_i < b_i.

Вхідні дані

У першому рядку знаходиться кількість тестів $N$ . Кожен тест задано одним рядком, що описує структуру намиста. Максимальна довжина намиста — $10000$ символів. Кожна намистина позначається малою літерою англійського алфавіту ( $a$ - $z$ ), де $a < b < \dots < z$ a < b < \ldots < z.

Вихідні дані

Для кожного тесту виведіть одне ціле число в окремому рядку — номер намистини, що стоїть першою при найгіршому можливому роз'єднанні, тобто таке $i$ , що рядок $A [i]$ є лексикографічно найменшим серед усіх $n$ можливих розривів намиста. Якщо існує кілька рішень, виведіть те, у якого $i$ найменше.

Приклади

Приклад 1