#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

mt19937 rng(7447);

const int N = 256;
int mp[N];

void solve()
{
	int m;
	string s;
	cin >> m >> s;
	VI v(m);
	iota(ALL(v), 0);
	vector<ULL> pw(SZ(s));
	pw.back() = 1;
	RFOR (i, SZ(s) - 1, 0)
		pw[i] = pw[i + 1] * m;
	
	int MAGIC = max(m, SZ(s)) + 7;
	
	ULL g = 0;
	int cnt = 0;
	FOR (iter, 0, 74)
	{
		shuffle(ALL(v), rng);
		if (v[0] == 0)
			continue;
		ULL x = 0;
		int idx = 0;
		FOR (i, 0, SZ(s))
		{
			int id = s[i] - 'a';
			if (mp[id] == -1)
				mp[id] = v[idx++];
			x += pw[i] * mp[id];
		}
		ULL g2 = __gcd(g, x);
		if (g2 == g)
			cnt++;
		else
		{
			g = g2;
			cnt = 0;
		}
		if (cnt == MAGIC)
			break;
			
		FOR (i, 0, SZ(s))
			mp[s[i] - 'a'] = -1;
	}
	cout << g << '\n';
	
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	fill(mp, mp + N, -1);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}