1972. Hidden Password

单点时限: 2.0 sec

内存限制: 256 MB

Some time the programmers have very strange ways to hide their passwords. See for example

how Billy “Hacker” Geits hide his password. Billy chooses a string S composed of small Latin letters with length L. Then he makes all L-1 one-letter left cyclic shifts of the string and takes as a password one prefix of the lexicographically first of the obtained strings (including S). For example let consider the string alabala. The cyclic one-letter left shifts (including the initial string) are:

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

and lexicographically first of them is the string aalabal. The first letter of this string is in position 6 in the initial string (the positions in the string are counted from 0).

Write a program that for given string S finds the start position of the smallest lexicographically one-letter left cyclic shift of this string. If the smallest lexicographically left shift appears more than once then the program have to output the smallest initial position.

输入格式

Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number T of the test cases. Each of the following T lines will describe one test case – first the length L of the string (5≤L≤100000) and then, separated by one space, the string S itself.

输出格式

The output file have to contain exactly T lines with a single number each – the initial position found by your program.

样例

Input
2
6 baabaa
7 alabala
Output
1
6

4 人解决,5 人已尝试。

11 份提交通过,共有 19 份提交。

7.1 EMB 奖励。

创建: 12 年,3 月前.

修改: 2 年,11 月前.

最后提交: 4 年,3 月前.

来源: Southeastern Europe 2003

题目标签