E

#include <bits/stdc++.h>
using namespace std;

#define ll     long long
#define ff     first
#define ss     second
#define pb     push_back

int main()
{
    int test;
    cin>>test;

    vector<vector<int>> div(200005);

    for(int i=1; i<=200000; i++){
        for(int j=i; j<=200000; j+=i)
            div[j].pb(i);
    }

    while(test--){
        int n;
        string s;
        cin>>n>>s;

        for(auto e: div[n]){
            int cnt = 0;

            for(int i=e; i<n && cnt<=1; i++)
                cnt += (s[i] != s[i%e]);

            if(cnt <= 1){
                cout<<e<<"\n";
                break;
            }

            cnt = 0;

            for(int i=2*e; i<n && cnt<=1; i++)
                cnt += (s[i] != s[e + i%e]);
            for(int i=0; i<e && cnt<=1; i++)
                cnt += (s[i] != s[e + i%e]);

            if(cnt <= 1){
                cout<<e<<"\n";
                break;
            }
        }
    }
}