题目描述

从前有一位著名的女演员。正如你所料，她主要演出古典喜剧，深受人们喜爱。但她对人群并不感兴趣，她最大的爱好是收集各种珠子。许多珠宝匠为她工作，每天制作新的项链和手链。有一天，她召见了首席珠宝匠督察（IBM），要求制作一条非常长且特殊的项链。

这条项链应由不同大小的玻璃珠连接而成，但珠子之间不能穿线，这意味着可以在任意位置断开项链。女演员选定了她想要的珠子排列顺序，IBM答应制作这条项链。但他随后意识到一个问题：相邻珠子之间的连接并不十分牢固，项链可能会因自身重量而断裂。当项链断开时情况会更糟，而且断开点的位置非常重要——如果断开点附近是小珠子，断裂的可能性远高于大珠子附近。IBM需要测试项链的牢固程度，因此需要一个能确定最差断开点的程序。

项链的描述是一个字符串$A = a_1a_2...a_m$，表示各个珠子的大小，其中最后一个字符$a_m$在环形结构中视为$a_1$的前驱。断开点$i$比断开点$j$更差的条件是：字符串$a_ia_{i+1}...a_na_1...a_{i-1}$在字典序上小于字符串$a_ja_{j+1}...a_na_1...a_{j-1}$。字符串$a_1a_2...a_n$字典序小于$b_1b_2...b_n$的条件是：存在整数$i \leq n$，使得对所有$j < i$有$a_j=b_j$，且$a_i < b_i$。

输入格式

输入包含$N$个测试用例。第一行仅包含正整数$N$。随后每个用例占一行，描述项链的珠子排列。每个描述的最大长度为$10000$个字符，每个珠子用一个小写字母（a-z）表示，其中$a < b < ... < z$。

输出格式

对于每个测试用例，输出一行一个整数，表示在最差断开点时第一个珠子的编号（即所有可能断开方式中字典序最小的字符串的起始位置）。若存在多个解，输出编号最小的那个。

输入样例

4
helloworld
amandamanda
dontcallmebfu
aaabaaa

输出样例

10
11
6
5

题目来源

$1998$年中欧地区竞赛