#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int t = 1;
    cin >> t;
    while(t-->0)
    {
        int n;
        cin >> n;

        string s;
        cin >> s;

        unordered_map<char, ll> val;
        ll now = 1;
        for(int i=s.size()-1; i>=0; i--)
        {
            val[s[i]] += now;
            now *= n;
        }

        if(val.size()==n)
        {
            if(n==2)
            {
                cout << val[s[0]] << "\n";
            }
            else
            {
                ll ans = 0, now = 0, cnt = 0;
                for(auto i: val)
                {
                    now += i.second*cnt;
                    cnt++;
                    for(auto j: val)
                    {
                        ans = __gcd(ans, abs(i.second - j.second));
                    }
                }
                cout << __gcd(now, ans) << "\n";
            }
        }
        else
        {
            ll ans = 0;
            for(auto i: val)
            {
                ans = __gcd(ans, i.second);
            }
            cout << ans << "\n";
        }
    }
}
/*
2
16 abcdefghijklmnop
16 qwertyuiopasdfgh
*/