#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;
        reverse(all(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;
        }
        ll rs = 0;
        for (ll r = 0; r < 50; r += 1) {
            shuffle(all(p), rnd);
            if (p[a[0]] == 0) {
                continue;
            }
            unsigned ll x = 0;
            for (int i = 0; i < n; i += 1) {
                x = x * m + p[a[i]];
            }
            rs = gcd(rs, x);
        }
        cout << rs << "\n";
    }
    return 0;
}