#pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("avx,avx2")


#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);
const ll mod = 1e9 + 7;
typedef complex<flt> base;
const flt pi = atan2(1, 0) * 2;





int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    for (int itr = 0; itr < t; itr += 1) {
        int m;
        string s;
        cin >> m >> s;
        string f = s;
        sort(all(f));
        f.resize(unique(all(f)) - f.begin());
        assert((int)f.size() <= m);
        int n = (int)s.size();
        vector<int> a(n);
        for (int i = 0; i < n; i += 1) {
            a[i] = lower_bound(all(f), s[i]) - f.begin();
        }
        vector<int> p(m);
        for (int i = 0; i < m; i += 1) {
            p[i] = i;
        }
        unsigned ll rs = 0;
        unsigned ll x = 0;
        shuffle(all(p), rnd);
        for (int i = 0; i < n; i += 1) {
            x = x * m + p[a[i]];
        }
        vector<unsigned ll> vals(m);
        unsigned ll pwr = 1;
        for (int i = n - 1; i >= 0; i -= 1) {
            vals[a[i]] += pwr;
            pwr *= m;
        }
        for (ll r = 0; r < 60; r += 1) {
            for (int aboba = 0; aboba < 8; aboba += 1) {
                int i = rnd() % m;
                int j = rnd() % m;
                x -= vals[i] * p[i] + vals[j] * p[j];
                swap(p[i], p[j]);
                x += vals[i] * p[i] + vals[j] * p[j];
            }
            /*
            shuffle(all(p), rnd);
            if (p[a[0]] == 0) {
                continue;
            }
            unsigned ll x = 0;
            for (int i = 0; i < m; i += 1) {
                x += vals[i] * p[i];
            }
            */
            if (rs == 0) {
                rs = x;
            } else if (x % rs != 0) {
                rs = gcd(rs, x);
            }
        }
        cout << rs << "\n";
    }
    return 0;
}

/*
1
16 abcdefghijklmnop

*/