Однажды жила известная актриса. Как вы уже догадались, больше всего она предпочитала играть античные комедии. Все люди любили ее. Однако она не была заинтересована в толпе. Ее наибольшим хобби были бусинки любого вида. Многие производители бус работали на нее, изготавливая новые ожерелья и браслеты каждый день. Как-то раз она позвонила своему главному инспектору бисера и сообщила, что хочет приобрести очень длинное и специальное ожерелье. Ожерелье должно быть выполнено из стеклянных бусинок разного размера, соединенных друг с другом. Однако никакая нить не должна проходить через бусинки - в произвольный момент времени должна присутствовать возможность отсоединять любую бусинку. Актриса выбрала последовательность бусинок и хочет сделать из них ожерелье. Однако потом поняла проблему. Соединение между двумя соседними бусинками не слишком надежно, поэтому ожерелье может разорваться под действием собственного веса. Ситуация становится еще хуже, если ожерелье распадется на части. Точки соединения бусинок являются очень важными. Если маленькие бусинки находятся в начале, то возможность разрыва ожерелья гораздо выше, чем если бы там были большие бусинки. Производитель бус хочет проверить надежность ожерелья и нуждается в программе, которая сможет определить точку наиболее возможного разрыва. Ожерелье задается строкой \textbf{A = a_1a_2 ... a_m}, описывающей размеры бусинок. Ожерелье замкнуто, поэтому после бусинки \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} наименьшее.