#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;
	ll tt=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]);
		}
//		cout<<endl;
		if(cnt==m){
			int mn=100,gg=m&1?m/2:m-1;
			for(int i=1;i<=26;++i)
				if(c[i]) mn=min(mn,c[i]);
			for(int i=1;i<=26;++i)
				if(c[i]>mn) gg=__gcd(gg,c[i]-mn);
			g=g/__gcd(g,gg)*gg;
		}
		cout<<g<<endl;
		if (tt==237&&tt-t==79){
			cerr<< m<<endl;
			for(ll i=1;i<=n;i++)cerr<<s[i];
		}
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:8:9: error: ‘ll’ was not declared in this scope
    8 |         ll tt=t;
      |         ^~
answer.code:45:21: error: ‘tt’ was not declared in this scope; did you mean ‘tm’?
   45 |                 if (tt==237&&tt-t==79){
      |                     ^~
      |                     tm
answer.code:47:31: error: expected ‘;’ before ‘i’
   47 |                         for(ll i=1;i<=n;i++)cerr<<s[i];
      |                               ^~
      |                               ;
answer.code:47:36: error: ‘i’ was not declared in this scope
   47 |                         for(ll i=1;i<=n;i++)cerr<<s[i];
      |                                    ^