#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define data dataa
using LL=long long;
using ULL=unsigned long long;
using LD=long double;
int main()
{
    int T;
    for(scanf("%d",&T);T--;)
    {
        int m;
        char p[20];
        scanf("%d%s",&m,p+1);
        int n=strlen(p+1);
        ULL pw[20];
        pw[0]=1;
        rep(i,n-1)pw[i]=pw[i-1]*m;
        map<char,ULL>dic;
        rep(i,n)dic[p[i]]+=pw[n-i];
        ULL a[20];
        int cnt=0;
        a[cnt=1]=dic[p[1]];
        ULL ans=a[1];
        for(auto [x,y]:dic)
        {
            if(x==p[1])continue;
            a[++cnt]=y;
            ans+=y*(cnt==2?0:cnt-1);
        }
        if(m==2){printf("%llu\n",ans);continue;}
        sort(a+1,a+cnt+1);
        // for(int i=2;i<=cnt;i++)rep(j,i-1)ans=gcd(ans,a[i]-a[j]);
        if(cnt<m)rep(i,cnt)ans=gcd(ans,a[i]);else ans=gcd(ans,m-1);
        printf("%llu\n",ans);
    }
    return 0;
}