Glass Beads

Once upon a time there was a famous actress whose great hobby was collecting glass beads of every kind. Many bead makers worked for her, crafting new necklaces and bracelets every day. One day she asked for a very long and special necklace.

The necklace is made of glass beads of different sizes joined to one another without any thread running through them, so it can come apart at any point between two neighbouring beads. Because the joints are fragile, the necklace may tear under its own weight, and the point where it comes apart matters: the smaller the beads at the beginning, the more likely it is to tear. We therefore need to find the worst (most dangerous) point at which the necklace could come apart.

The necklace is described by a string A = a_1 a_2 … a_m giving the sizes of the beads. It is circular, so the last character a_m is followed again by the first character a_1.

A disjoining point i is worse than a disjoining point j if and only if the string a_i a_{i+1} … a_m a_1 … a_{i-1} is lexicographically smaller than the string a_j a_{j+1} … a_m a_1 … a_{j-1}. A string x_1 x_2 … x_n is lexicographically smaller than a string y_1 y_2 … y_n if and only if there is an integer k (1 ≤ k ≤ n) such that x_j = y_j for every j with 1 ≤ j < k, and x_k < y_k.

The first line contains a single positive integer N, the number of cases. Each of the following N lines contains one necklace description. Each description has length at most 10000, and each bead is a lower-case English letter ('a' to 'z'), where 'a' < 'b' < … < 'z'.

For each case, print a single line containing one integer: the number i of the bead that comes first at the worst disjoining point, i.e. the index i for which the string obtained by starting at bead i and going around the necklace is lexicographically smallest among all n rotations. If several indices give the smallest string, print the smallest such i. Beads are numbered from 1.