Hidden Password#5752
Programmers sometimes use very strange ways to hide their passwords. For example, consider how Billy "Hacker" Gates hides his password. Billy chooses a string consisting of lowercase Latin letters, of length . Then, he makes all l-1 possible one-letter left cyclic shifts of the string and considers, among all strings (including itself), the lexicographically smallest one. Billy then uses a prefix of this smallest string as his password.
For example, consider the string alabala. The one-letter left cyclic shifts (including the original string) are:
alabala labalaa abalaal balaala alaalab laalaba aalabal
The lexicographically first among them is aalabal. The first letter of this string is at position in the original string (positions are numbered starting from ).
Write a program that, for a given string , finds the starting position of the lexicographically smallest one-letter left cyclic shift of this string. If this smallest shift occurs more than once, output the smallest such starting position.
The first line contains the integer — the number of test cases.
Each test case consists of two lines. The first line contains the integer (5 \leq l \leq 100\,000) — the length of the string. The second line contains the string itself.
Output exactly lines. For each test case, print a single integer — the initial position found by your program.
Example 1