#include<bits/stdc++.h>
using namespace std;
const int ans[]={0,0,2,1,3,2,5,3,7,4,9,5,11,6,13,7,15};
mt19937 mt(time(NULL));
constexpr int M=30;char s[M];
int n,d,num,T,f[M],vec[M];
unsigned long long sum,gcd,g[M],pw[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
int main(){
	scanf("%d",&T); while (T--){
		scanf("%d%s",&d,s+1);n=strlen(s+1);
		for (int i=pw[0]=1;i<=n;i++) pw[i]=pw[i-1]*d;
		for (int i=0;i<26;i++) g[i]=0; iota(f,f+d,0);
		for (int i=1;i<=n;i++) g[s[i]-'a']+=pw[n-i]; num=0;
		for (int i=0;i<26;i++)
			if (g[i]) vec[num++]=i;
		if (num==d&&d==n) {printf("%d\n",ans[d]);continue;}
		if (num>d) {puts("0");continue;}
		int t=num>=10?80:num>=5?70:60;gcd=0;
		while (t--){ sum=0;bool fl=1;
			for (int i=0;i<num;i++){
				sum+=f[i]*g[vec[i]];
				if (!f[i]&&vec[i]==s[1]-'a')
					{fl=0;break;}
			}
			if (fl) gcd=__gcd(gcd,sum);
			shuffle(f,f+d,mt);
			if (gcd==1) break;
		}
		printf("%llu\n",gcd);
	}
	return 0;
}