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

using i64 = long long;
using u64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;

    auto solve = [&]() {
        int m;
        string p;
        cin >> m >> p;

        int n = p.size();
        vector<u64> pw(n);
        pw[0] = 1;
        for (int i = 1; i < n; i++) {
            pw[i] = pw[i - 1] * m;
        }

        if (m == 2) {
            u64 ans = 0;
            for (int i = 0; i < n; i++) {
                if (p[i] == p[0]) {
                    ans += pw[n - 1 - i];
                }
            }
            cout << ans << '\n';
            return;
        }

        map<char, u64> mp;
        for (int i = 0; i < n; i++) {
            mp[p[i]] += pw[n - 1 - i];
        }

        vector<u64> vec;
        for (auto x : mp) { vec.push_back(x.second); }
        vec.resize(m);
        sort(vec.begin(), vec.end());

        u64 ans = 0;
        for (int i = 0; i < m; i++) {
            ans += i * vec[i];
        }

        for (int i = 1; i < m; i++) {
            ans = gcd(ans, vec[i] - vec[0]);
        }

        cout << ans << '\n';
    };

    while (t--) {
        solve();
    }
    
    return 0;
}