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 \textbf{s} composed of small Latin letters with length \textbf{l}. Then he makes all \textbf{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 \textbf{s}). For example let consider the string \textbf{alabala}. The cyclic one-letter left shifts (including the initial string) are: \textbf{alabala} \textbf{labalaa} \textbf{abalaal} \textbf{balaala} \textbf{alaalab} \textbf{laalaba} \textbf{aalabal} and lexicographically first of them is the string \textbf{aalabal}. The first letter of this string is in position \textbf{6} in the initial string (the positions in the string are counted from \textbf{0}). Write a program that for given string \textbf{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. \InputFile The first line contains the number \textbf{t} of the test cases. The first line of each test case contains the length \textbf{l }of the string (\textbf{5 }≤ \textbf{l} ≤ \textbf{100000}) and the second line contains the string \textbf{s} itself. \OutputFile The output file have to contain exactly \textbf{t} lines with a single number each - the initial position found by your program.