숨겨진 비밀번호

프로그래머들은 때때로 이상한 방법으로 비밀번호를 숨긴다. Billy "Hacker" Geits가 자신의 비밀번호를 숨기는 방법을 보자. Billy는 길이가 $L$인 소문자 라틴 문자열 $S$를 고른다. 그런 다음 이 문자열을 한 글자씩 왼쪽으로 순환 이동시킨 $L-1$개의 문자열을 모두 만들고, ($S$ 자신을 포함한) 이 문자열들 중 사전순으로 가장 앞선 것의 접두사를 비밀번호로 삼는다.

예를 들어 문자열 alabala를 생각해 보자. (원래 문자열을 포함한) 한 글자 왼쪽 순환 이동 결과는 다음과 같다.

alabala
labalaa
abalaal
balaala
alaalab
laalaba
aalabal

이들 중 사전순으로 가장 앞선 것은 aalabal이다. 이 문자열의 첫 글자는 원래 문자열에서 위치 $6$에 있다. (위치는 $0$부터 센다.)

문자열 $S$가 주어질 때, 이 문자열의 사전순으로 가장 앞선 한 글자 왼쪽 순환 이동의 시작 위치를 찾는 프로그램을 작성하시오. 가장 앞선 순환 이동이 여러 번 나타나면 가장 작은 시작 위치를 출력한다.

입력의 첫째 줄에는 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 하나의 테스트 케이스가 주어진다. 먼저 문자열의 길이 $L$ ($5 \le L \le 100000$)이 주어지고, 공백 하나로 구분되어 문자열 $S$가 주어진다.

정확히 $T$개의 줄을 출력하며, 각 줄에는 해당 테스트 케이스에 대해 찾은 시작 위치를 하나의 수로 출력한다.