#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
inline ll gcd(ll x,ll y) { return y?gcd(y,x%y):x; }
ll f[30];
char s[30];
inline void solve() {
	int n,m;
	scanf("%d%s",&m,s+1),n=strlen(s+1);
	memset(f,0,sizeof(f));
	for(ll p=1,i=n;i>=1;--i) f[s[i]-'a']+=p,p*=m;
	vector <ll> F;
	for(int i=0;i<26;++i) if(f[i]) F.push_back(f[i]);
	if(m==2) return printf("%llu\n",f[s[1]-'a']),void();
	F.resize(m),sort(F.begin(),F.end());
	ll ans=0;
	for(int i=1;i<m;++i) ans=gcd(ans,F[i]-F[i-1]);
	printf("%llu\n",ans);
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}