Hidden Password

Billy chooses a string S of L lowercase Latin letters. Consider S and all of its one-letter left cyclic shifts. Find the starting position, in the original string, of the lexicographically smallest shift. Positions are numbered from 0. If the smallest shift occurs more than once, print its smallest starting position.

For example, the shifts of alabala are alabala, labalaa, abalaal, balaala, alaalab, laalaba, and aalabal. The smallest starts at position 6.

Input

The first line contains the number of test cases T. Each test case contains an integer L and a string S, separated by one space, where 5 \le L \le 100000 and |S|=L.

Output

For each test case, print the required zero-based starting position.

Example

Input:

2
6 baabaa
7 alabala

Output:

1
6