Description

Given a string of length len, we can form a circular loop with it. 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, consider the string alabala. When formed into a circular loop, the following new strings can be generated:

• labalaa
• abalaal
• balaala
• alaalab
• laalaba
• aalabal

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

Now, 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 contains an integer t, representing the number of test cases.

Each of the next t lines contains an integer l (5 ≤ l ≤ 100000), representing the length of the original string, followed by the string itself. The string consists only of lowercase letters.

Output Format

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

2
6 baabaa
7 alabala

1
6

Source

CodesOnline