#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+;

char s[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    int T; scanf("%d",&T);

    while(T--){

        int n; scanf("%d",&n);

        scanf("%s",s);

        int i = ,j = , k = ;

        while(i<n && j<n && k<n){

            int x = (i+k)%n, y = (j+k)%n;

            if(s[x] != s[y]){

                if(s[x] > s[y]) i += k+;//如果不移动到这里，另外一边一定存在一个更小的前缀

                else j += k+;

                k = ;

            }else k++;

            if(i == j) j++;

        }

        printf("%d\n",i);

    }

    return ;

}