/*
think:30min
maybe it's really trivial
maybe I need 30min to solve it
coding:12:05
failure
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20;
int t,m,n,ret,ans,l;
char p[MAXN];
bool vis[MAXN],flag;
int w[210];
long long v[MAXN],s;
int num,now;
long long fans,pw[MAXN];
long long gcd(long long x,long long y)
{
	return y==0?x:gcd(y,x%y);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %s",&m,p+1);
		pw[0]=1;
		for(int i=1;i<=16;i++) pw[i]=pw[i-1]*m;
		l=strlen(p+1);
		for(int i=1;i<=l/2;i++) swap(p[i],p[l-i+1]);
		ret=0;
		for(int i=0;i<l;i++)
		{
			for(int j=1;j<=l;j++)
			{
				if((i+1)*(j-1)+1>l) continue;
				memset(vis,0,sizeof(vis));
				flag=0;
				for(int k=1;k<=l;k++)
				{
					if(flag) break;
					if(!vis[k])
					{
						vis[k]=1;
						for(int o=1;o<=j-1;o++)
						{
							if(k+o*(i+1)>l||vis[k+o*(i+1)]||p[k+o*(i+1)]!=p[k])
							{
								flag=1;
								break;
							}
							vis[k+o*(i+1)]=1;
						}
					}
				}
				if(!flag)
				{
					now=0;
					for(int k=1;k<=j;k++)
						now|=1<<((k-1)*(i+1));
					ret=max(ret,now);
				}
			}
		}
		if(__builtin_popcount(ret)!=n)
		{
			ans=m-1;
			memset(vis,0,sizeof(vis));
			now=0;
			num=0;
			for(int i=1;i<=l;i++)
			{
				if(!((1<<i-1)&now))
				{
					if(!w[p[i]]) w[p[i]]=++num;
					v[w[p[i]]]+=pw[i-1];
					now|=ret<<i-1;
				}
			}
			for(int i=1;i<=l;i++) w[p[i]]=0;
			if(num==m)
			{
				for(int i=1;i<num;i++)
					ans=gcd(ans,abs(v[i]-v[i+1]));
			}
			else
			{
				for(int i=1;i<=num;i++)
					ans=gcd(ans,v[i]);
			}
			s=0;
			for(int i=1;i<=num;i++) s+=v[i]*(i-1);
			for(int i=1;i<=num;i++) v[i]=0;
			ans=gcd(ans,s);
		}
		fans=0;
		for(int i=1;i<=l;i++)
			if(ret&(1<<i-1)) fans+=pw[i-1];
		fans*=ans;
		printf("%lld\n",fans);
	}
	return 0;
}