Glass Beads#2912

Glass Beads

1 second

10 megabytes

Very easy

Once upon a time, there was a famous actress. As you may expect, she most enjoyed performing in Ancient Comedies. Everyone loved her, but she was not interested in the crowds. Her biggest hobby was collecting beads of all kinds. Many bead makers worked for her, producing new necklaces and bracelets every day. One day, she called her main Inspector of Bead Makers (IBM) and told him she wanted a very long and special necklace.

The necklace should be made of glass beads of different sizes, each connected together, but with no thread passing through the beads—so that any bead can be disconnected at any moment. The actress chose the sequence of beads she wanted, and the IBM promised to make the necklace. But then came a problem: the joint between two neighboring beads is not very reliable, so the necklace might tear under its own weight. The situation gets even worse if the necklace becomes separated. The points where the beads are joined are very important. If small beads are at the beginning, the chance of tearing is higher than if there were large beads. The bead maker wants to check the reliability of the necklace and requires a program to determine the worst possible point of separation.

The necklace is described by a string $A = a_{1} a_{2} \dots a_{m}$ A = a_1 a_2 \ldots a_m specifying the sizes of the particular beads; the necklace is circular, so the bead $a_{m}$ a_m is followed by $a_{1}$ a_1.

A joint at position $i$ is said to be worse than a joint at position $j$ if and only if the string $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} is lexicographically smaller than the string $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}. The string $a_{1} a_{2} \dots a_{n}$ a_1 a_2 \ldots a_n is lexicographically smaller than the string $b_{1} b_{2} \dots b_{n}$ b_1 b_2 \ldots b_n if there exists an integer $i$ ( $i \leq n$ i \leq n) such that $a_{j} = b_{j}$ a_j = b_j for each $j$ ( $1 \leq j < i$ 1 \leq j < i), and $a_{i} < b_{i}$ a_i < b_i.

Input

The first line contains the number of test cases $N$ . Each test case is given on a single line describing the structure of the necklace. The maximum necklace length is $10000$ characters. Each bead is represented by a lowercase letter of the English alphabet ( $a$ - $z$ ), where $a < b < \dots < z$ a < b < \ldots < z.

Output

For each test case, output a single integer on its own line—the number of the bead that comes first at the worst possible joint, that is, such $i$ that the string $A [i]$ is lexicographically smallest among all $n$ possible separations of the necklace. If there are multiple solutions, print the one with the smallest $i$ .

Examples

Example 1