#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int T,n,m,tot;
int mp[40];
__int128 ans;
__int128 mul[40],sum[40];
string s;
__int128 bigabs(__int128 x){
	return x<0? -x:x;
}
__int128 biggcd(__int128 a,__int128 b){
	return b==0? a:biggcd(b,a%b);
}
void print(__int128 x){
	if(x>9)
		print(x/10);
	putchar(x%10+48);
}
int main(){
	ios::sync_with_stdio(false),cin>>T;
	while(T--){
		memset(mp,0,sizeof(mp)),memset(sum,0,sizeof(sum));
		ans=tot=0;
		cin>>m>>s,n=s.size();
		mul[0]=1;
		for(int i=1;i<=n;i++)
			mul[i]=mul[i-1]*m;
		for(int i=0;i<n;i++){
			if(mp[s[i]-96]==0)
				mp[s[i]-96]=++tot,sum[tot]=0;
			sum[mp[s[i]-96]]+=mul[n-i-1],ans=ans*m+mp[s[i]-96]-1;
		}
		sort(sum+1,sum+1+tot);
		for(int i=1;i<tot;i++)
			ans=biggcd(ans,bigabs(sum[i+1]-sum[i]));
		print(ans),putchar('\n');
	}
	return 0;
}