#include <iostream>
#include <bits/stdc++.h>

using namespace std;


const int MAXN = 1e5 + 5;

struct entry{
    //p[k-1][i] , p[k-1][i + s^(k-1)]
    int pi[2];
    int ind;
}L[MAXN];

bool comp(entry p1, entry p2){
    return (p1.pi[0] == p2.pi[0]) ? (p1.pi[1] < p2.pi[1]) : (p1.pi[0] < p2.pi[0]);
}

int P[(int)ceil(log2(MAXN)) + 1][MAXN];

vector<pair<int,int> > vec[MAXN];
vector<pair<int,int> > countSort(vector<pair<int,int> > &vecc){
    vector<int> cnt(MAXN , 0);
    for(int i=0;i<vecc.size();i++){
        cnt[vecc[i].first]++;
    }
    for(int i=0;i<MAXN;i++){
        cnt[i] += i > 0 ? cnt[i-1] : 0;
    }
    vector<pair<int,int> > sorted(vecc.size());
    for(int i=0;i<vecc.size();i++){
        sorted[cnt[vecc[i].first] - 1] = vecc[i];
        cnt[vecc[i].first]--;
    }
    return sorted;
}


void suffixArray(string str , bool fast){
    vector<pair<char,int> > tmp;
    for(int i=0;i<str.length();i++){
        tmp.push_back({str[i],i});
    }
    sort(tmp.begin(),tmp.end());
    for(int i=0;i<tmp.size();i++){
        P[0][tmp[i].second] = i > 0 && tmp[i].first == tmp[i-1].first ? P[0][tmp[i-1].second] : i;
    }

    int step = 1;
    for(; (step << 1) <= str.length() ; step++){
        for(int i=0;i<str.length();i++){
            L[i].pi[0] = P[step - 1][i];
            L[i].pi[1] = (i + (1 << (step - 1)) <= str.length()) ? P[step - 1][i + (1 << (step - 1))] : -1 ;
            L[i].ind = i;
        }


        //using counting sort if n * log^2(n) not working

        if(fast){
            for(int i=0;i<MAXN;i++){
                vec[i].clear();
            }
            for(int i=0;i<str.length();i++){
                vec[L[i].pi[0] + 1].push_back({L[i].pi[1] + 1 , L[i].ind});
            }
            for(int i=0;i<MAXN;i++){
                if(vec[i].size() > 0){
                    vec[i] = countSort(vec[i]);
                }
            }

            int ind = 0;
            for(int i=0;i<MAXN;i++){
                for(int j=0;j<vec[i].size();j++){
                    P[step][vec[i][j].second] = (j > 0 && vec[i][j].first == vec[i][j-1].first)? P[step][vec[i][j-1].second] : ind;
                    ind++;
                }
            }
        }

        //using normal sort easy to implement n * log^2(n)
        else{
            sort(L , L + MAXN , comp);
            for(int i=0;i<MAXN;i++){
                P[step][L[i].ind] = (i > 0 && L[i-1].pi[0] == L[i].pi[0] && L[i-1].pi[1] == L[i].pi[1]) ? P[step][L[i-1].ind] : i;
            }
        }
    }
}

int main()
{

//    int ans = 0;
//    for(int i=0;i<=(ceil(log2(str.length())));i++){
//        set<int> sety;
//        for(int j=0;j<str.size();j++){
//            if(j + (1<<i) - 1 >= str.length())continue;
//            sety.insert(P[i][j]);
//        }
//        ans+=sety.size();
//    }
//    cout << ans;


    int t;
    cin >> t;
    while(t--){
        int len;
        cin >> len;
        string str;
        cin >> str;
        suffixArray(str+str , true);

        int order = 1e9 , ind;
        for(int j=0;j<str.size();j++){
            if(P[(int)ceil(log2(str.length()))][j] < order){
                order = P[(int)ceil(log2(str.length()))][j];
                ind = j;
            }
        }
        cout << ind << "\n";
    }
    return 0;
}