BEADS - Glass Beads

题干部分： 很久很久以前，有一个非常出名的女星。就像你猜的那样，她经常表演喜剧。所有人都非常喜欢她。有很多制作首饰的人在为她服务，他们每天都会加工出新的项链、手链之类的首饰。有一天，她告诉首饰加工（IBM）的总负责人她想要一串特别长而且非常特别的项链。 这条项链是由一串大小不同的玻璃珠串成的，这些玻璃珠子之间互相紧密连接，但是没有线将它们串起来，所以这条项链可以在任何一个位置剪断。这个演员会选出一串她喜欢的珠子，并且这些加工者们保证可以提供她所需的任何珠子。但是，他们发现了一个非常严重的问题：珠子和珠子之间连接不够紧，导致这条项链很可能由于它自身的重量而断裂。更为重要的是，项链的断裂点非常重要。如果项链的断开的地方有一个比较小的珠子，那么项链断开的可能性就会比同样位置有一个大一些的珠子时项链断开的可能性大一些。现在，IBM希望测试这条项链的牢固程度。他们希望有一个程序来寻找项链最容易断裂，即断裂的可能性最高的地方。 给定一个字符串A=a1,a2,……am表示这条项链上每一个珠子的大小，并且当项链首尾相接形成一个环的时候，最后一个珠子am在第一个珠子a1的前面。 我们说一个断开的地方i比另一个断开的地方j要差当且仅当字符串a[i] a[i+1] ……a[n] a[1] ……a[i-1]的字典序小于a[j] a[j+1]……a[n] a[1]……a[j-1]。字符串A（a1,a2,a3……an）的字典序比字符串B（b1,b2,b3……bn）要小当且仅当存在一个整数i且i≤n使得存在一个整数j使得1≤j＜i且ai＜bi。 输入格式： 输入的第一行包含一个整数N，表示输入数据的组数。接着是N组数据，每组数据包含一个字符串表示项链上的所有珠子。每一组数据的长度不超过10000个字符。所有的珠子都用一个小写的英语字母表示，它们的字典序按照英文字母表的顺序确定。 输出格式： 对于每一组数据，输出一行，包含一个整数，代表最差的情况中首颗珠子的编号。这个答案满足：字符串（代表分割情况）A[i]的字典序在所有的字符串中是最小的。如果答案不唯一，输出最小的i。 感谢@张文思 提供的翻译

Once upon a time there was a famous actress. As you may expect, she played mostly Antique Comedies most of all. All the people loved her. But she was not interested in the crowds. Her big hobby were beads of any kind. Many bead makers were working for her and they manufactured 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 connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not very robust so it is possible that the necklace will get torn by its own weight. The situation becomes even worse when the necklace is disjoined. Moreover, the point of disconnection is very important. If there are small beads at the beginning, the possibility of tearing is much higher than if there were large beads. IBM wants to test the robustness of a necklace so he needs a program that will be able to determine the worst possible point of disjoining the beads. The description of the necklace is a string A = a $ _{1} $ a $ _{2} $ ... a $ _{m} $ specifying sizes of the particular beads, where the last character a $ _{m} $ is considered to precede character a $ _{1} $ in circular fashion. The disjoint point i is said to be worse than the disjoint point j if and only if the string a $ _{i} $ a $ _{i+1} $ ... a $ _{n} $ a $ _{1} $ ... a $ _{i-1} $ is lexicografically smaller than the string a $ _{j} $ a $ _{j+1} $ ... a $ _{n} $ a $ _{1} $ ... a $ _{j-1} $ . String a $ _{1} $ a $ _{2} $ ... a $ _{n} $ is lexicografically smaller than the string b $ _{1} $ b $ _{2} $ ... b $ _{n} $ if and only if there exists an integer i, i <= n, so that a $ _{j} $ =b $ _{j} $ , for each j, 1 <= j < i and a $ _{i} $ < b $ _{i} $ .

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line containing necklace description. Maximal length of each description is 10000 characters. Each bead is represented by a lower-case character of the english alphabet (a--z), where a < b ... z.

For each case, print exactly one line containing only one integer -- number of the bead which is the first at the worst possible disjoining, i.e. such i, that the string A\[i\] is lexicographically smallest among all the n possible disjoinings of a necklace. If there are more than one solution, print the one with the lowest i.

4
helloworld
amandamanda
dontcallmebfu
aaabaaa

10
11
6
5