#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
using ull=unsigned long long;
const int N=18;
int T,m,n,k;
ull v[N],vis[128];
char a[N];
void get(){
	scanf("%d%s",&m,a+1),n=strlen(a+1);
	ull now=1;
	for(int i=n;i>=1;i--,now*=m){
		vis[a[i]]+=now;
	}
	k=0;
	for(int i=1;i<=n;i++)if(vis[a[i]]){
		v[++k]=vis[a[i]],vis[a[i]]=0;
	}
	if(k==1){
		printf("%llu\n",v[1]);
		return;
	}
	if(k<m){
		ull ans=0;
		for(int i=1;i<=k;i++)ans=__gcd(ans,v[i]);
		printf("%llu\n",ans);
		return;
	}
	if(m==2){
		printf("%llu\n",v[1]);
		return;
	}
	ull ans=0;
	for(int i=1;i<=k;i++){
		ans+=v[i]*(i%k);
	}
	for(int i=2;i<=k;i++){
		ans=__gcd(ans,max(v[1],v[i])-min(v[1],v[i]));
	}
	printf("%llu\n",ans);
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}