#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

ll p[55];

int main(){
	ll t;
	cin >> t;
	while (t--){
		ll m;
		string s;
		cin >>m>> s;
		if (m==2){
			ll pw=0;
			for (ll i=0;i<s.length();i++){
				if (s[i]==s[0])pw*=2,pw++;
				else pw*=2;
			}
			cout<<pw<<"\n";
			continue;
		}
		for (ll j=0;j<26;j++)p[j]=0;
		set<char> st;
		for (ll i=0;i<s.length();i++){
			st.insert(s[i]);
			for (ll j=0;j<26;j++){
				if (s[i]-'a'!=j){
					p[j]*=m;
				}else{
					p[j]*=m;
					p[j]++;
				}
			}
		}
		ll ans=0;
		map<char,ll> mp;
		ll nw=m-1;
		for (ll i=0;i<s.length();i++){
			if (mp[s[i]]){
				ans*=m,ans+=mp[s[i]]-1;
			}else{
				mp[s[i]]=nw+1;
				nw--;
				ans*=m,ans+=mp[s[i]]-1;
			}
		}
		if (st.size()!=m)
		for (ll j=0;j<26;j++)if (p[j])ans=__gcd(ans,p[j]);
		for (ll i=0;i<26;i++){
			for (ll j=i+1;j<26;j++){
				if (p[i]&&p[j]){
					ans=__gcd(ans,abs(p[i]-p[j]));
				}
			}
		}
		cout<< ans<<"\n";
	}
	return 0;
}

/*
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/