Hidden Password

Programmers sometimes hide their passwords in strange ways. Here is how Billy "Hacker" Geits hides his. Billy picks a string $S$ of lowercase Latin letters with length $L$. He then forms all $L-1$ one-letter left cyclic shifts of the string and, among all of these strings (including $S$ itself), takes a prefix of the lexicographically smallest one as his password.

For example, take the string alabala. Its one-letter left cyclic shifts (including the original string) are:

alabala
labalaa
abalaal
balaala
alaalab
laalaba
aalabal

The lexicographically smallest of them is aalabal. Its first letter is at position $6$ in the original string (positions are counted from $0$).

Given a string $S$, write a program that finds the start position of its smallest lexicographic one-letter left cyclic shift. If the smallest shift occurs more than once, output the smallest start position.

The first line of input contains the number $T$ of test cases. Each of the next $T$ lines describes one test case: first the length $L$ of the string ($5 \le L \le 100000$), then, separated by one space, the string $S$ itself.

Output exactly $T$ lines, each containing a single number: the start position found for the corresponding test case.