#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
typedef unsigned long long ull;

inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f? -x : x;
}

ull sum[30];
template <class T>
T gcd(T a, T b) {return b? gcd(b, a % b) : a;}

template <class T>
inline T sub(T x, T y) {return x > y? x - y : y - x;}
int main() {
	int T = read();
	while (T--) {
		int m, p;
		m = read();
		static char str[20];
		scanf("%s", str + 1);
		p = strlen(str + 1);
		ull t = 1;
		for (int i = 1; i <= p; ++i) {
			sum[str[i] - 'a'] += t;
			t = t * m;
		}
		ull ss = 0;
		int cnt = 0;
		for (int i = 0; i < 26; ++i)
			if (sum[i]) ss += sum[i] * cnt, ++cnt;
		ull d = 0;
		if (cnt < m) {
			for (int i = 0; i < 26; ++i)
				if (sum[i]) d = gcd(d, sum[i]);
		}
		else {
			if (m == 2) {
				d = 1ull << (p - 1);
			}
			else {
				ull pre = 0;
				for (int i = 0; i < 26; ++i) {
					if (sum[i]) {	
						if (pre) d = gcd(d, sub(sum[i], pre));
						pre = sum[i];
					}
				}
				d = gcd(d, ss);
			}
		}
		for (int i = 0; i < 26; ++i) sum[i] = 0;
		printf("%llu\n", d);
	}
	return 0;
}