#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,n,m,a[30],c[30];
char s[30];
signed main(){
	cin>>t;
	while(t--){
		cin>>m>>s+1;
		n=strlen(s+1);
		if(m==2){
			int res=0;
			for(int i=1;i<=n;++i){
				res<<=1;
				if(s[i]==s[1]) ++res;
			}
			cout<<res<<endl;
			continue;
		}
		int g=0,cnt=0;
		for(int i=1;i<=26;++i) a[i]=c[i]=0;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=26;++j) a[j]*=m;
			++a[s[i]^96];
			++c[s[i]^96];
		}
		for(int i=1;i<=26;++i){
			if(!c[i]) continue;
//			cout<<a[i]<<" ";
			++cnt;
			if(!g) g=a[i];
			else g=__gcd(g,a[i]);
		}
		int s=0,cc=0;
		for(int i=1;i<=26;++i){
			if(!c[i]) continue;
			s+=cc*a[i];
			++cc;
		}
		g=__gcd(g,s);
//		cout<<endl;
		int mn=100,gg=m&1?m/2:m-1;
//		if(cnt==m){
			for(int i=1;i<=26;++i)
				if(c[i]) mn=min(mn,c[i]);
//		}
			if(mn==100) gg=m-1;
		for(int i=1;i<=26;++i)
			if(c[i]>mn) gg=__gcd(gg,c[i]-mn);
		g=g*gg;
		cout<<g<<endl;
	}
	return 0;
}