Identificador: asma-ae
Introducción
Érase una vez una famosa actriz. Toda la gente la quería, pero ella no estaba interesada en la multitud. Su gran afición eran los collares de cualquier tipo. Muchos fueron los responsables de cuentas que trabajaban para ella y fabricaban collares y pulseras nuevas todos los días. Un día ella llamó a su director principal de los fabricantes de abalorios y le dijo que quería un collar muy largo y especial.
El collar debía ser de cuentas de vidrio de diferentes tamaños, conectadas entre sí, pero sin ningún hilo conductor de las cuentas, de modo que, las cuentas pudieran ser desconectadas en cualquier momento. La actriz escogió la sucesión de cuentas que quería tener y el director se comprometió a hacer el collar. Pero entonces se dio cuenta de un problema. La junta entre dos cuentas vecinas no es muy robusta por lo que es posible que el collar se rompa por su propio peso. Además, el punto de desconexión es muy importante. Si hay cuentas pequeñas al principio, la posibilidad de romperse es mucho mayor que si hubiera cuentas grandes.
Tarea
El director quiere poner a prueba la solidez de un collar de modo que necesita un programa que sea capaz de determinar el punto más probable de desconectar las cuentas.
La descripción del collar es una cadena A = a1a2 ... am especificando los tamaños de las cuentas, donde el último carácter am se considera que precede el carácter a1 en forma circular.
Se dice que el punto de separación i es peor que el punto de separación j si y sólo si la cadena aiai+1 ... ana1 ... ai-1 es lexicográficamente menor que la cadena ajaj+1 ... ana1 ... aj-1. La cadena a1a2 ... an es lexicográficamente menor que la cadena b1b2 ... bn si y sólo si existe un entero i, i <= n, tal que aj=bj, para cada j, 1 <= j < i y ai < bi.
Entrada
La entrada consiste de N casos. La primera línea de la entrada contiene sólo un entero positivo N. Luego siguen los casos. Cada caso consiste exactamente una línea que contiene la descripción del collar. La longitud máxima de cada descripción es de 10000 caracteres. Cada cuenta está representada por una letra minúscula del alfabeto.
Salida
Para cada caso, imprimir exactamente una línea que contiene sólo un número entero - el número de la primera cuenta que tenga el peor punto de ruptura posible, es decir, la i tal, que la cadena] A[i] sea lexicográficamente más pequeña entre todas la posibles rupturas del collar. Si hay más de una solución, escribe la menor i.
Ejemplos de ejecución
Entrada
4
helloworld
amandamanda
dontcallmebfu
aaabaaa
Salida
10
11
6
5