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

int T;
int m;
string s;

const int MAXN = 35;
int cnt, tmp[MAXN];
long long a[MAXN];

long long llgcd(long long a,long long b) {
    return b==0 ? a : llgcd(b, a%b);
}
long long llabs(long long a) {
    return a<0 ? -a : a;
}

int main() {
    cin >> T;
    while(T--) {
        cin >> m >> s;
        cnt = 0;
        for( int i=0; i<26; i++) {
            tmp[i] = 0;
            a[i] = 0;
        }
        long long w = 1;
        for(int i = s.length()-1; i>=0; i--) {
            if(!tmp[s[i]-'a']) {
                cnt++;
                tmp[s[i]-'a'] = cnt;
            }
            int k = tmp[s[i]-'a'];
            a[k] += w;
            w *= m;
        }
        sort(a+1, a+cnt+1);

        long long ans = 0;
        if( cnt < m ) {
            for(int k=1; k<=cnt; k++) {
                ans = llgcd(a[k], ans);
            }
        }
        else {
            ans = 0;
            for(int k=cnt; k>=1; k--) {
                ans += a[k] * (cnt-k);
            }
            for(int k=1; k<cnt; k++) {
                ans = llgcd(a[k+1]-a[k], ans);
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}