#include<bits/stdc++.h>
using namespace std;
constexpr int M=30;
int n,d,num,T;char s[M];
unsigned long long gcd,f[M],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;
		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]) f[num++]=g[i];
		if (d==2) {printf("%d\n",g[s[1]-'a']);continue;}
		gcd=0;sort(f,f+num);
		for (int i=0;i<num;i++) gcd+=f[i]*i;
		for (int i=1;i<num;i++) gcd=__gcd(gcd,f[i]-f[i-1]);
		printf("%llu\n",gcd);
	}
	return 0;
}