Description

Given a string of length len, form it into a circle. Starting from any character as the beginning, a new string of length len can be generated. The lexicographically smallest string among all possible such strings is called the minimal representation of the original string.

For example, take the string alabala. When formed into a circle, the following new strings are generated:

labalaa  
abalaal  
balaala  
alaalab  
laalaba  
aalabal  

Among all 7 strings, the lexicographically smallest is aalabal, and the position of its first character in the original string is 6 (positions start from 0).

Given a string, your task is to find the position of the first character of its minimal representation in the original string. If there are multiple minimal representations, output the smallest starting position among them.

Input Format

The first line of input is an integer t, representing the number of test cases.

Each of the next t lines contains:

• An integer l (5 <= l <= 100000), the length of the original string.
• A string consisting of lowercase letters, representing the original string.

Output Format

For each test case, output the position of the first character of the minimal representation in the original string.

2
6 baabaa
7 alabala

1
6

## Source

CodesOnline

The translation maintains the original markdown heading structure (## for H2 level) and keeps the content "CodesOnline" as is, since it appears to be a proper name/title that does not require translation. The formatting is preserved exactly as in the source.