#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
namespace io {
    char ibuf[1 << 22], *ihd = ibuf, *itl = ibuf;
    char getc() {
        if (ihd == itl) {
            ihd = ibuf;
            itl = ibuf + fread(ibuf, 1, 1 << 22, stdin);
            if (ihd == itl) return EOF;
        }
        return *(ihd++);
    }
    char obuf[1 << 22], *otl = obuf;
    void putc(char c) {
        if (otl - obuf == 1 << 22) {
            fwrite(obuf, 1, 1 << 22, stdout);
            otl = obuf;
        }
        *(otl++) = c;
    }
    void flush() { fwrite(obuf, 1, otl - obuf, stdout); }
}  
using io::putc;
template <typename T>
void read(T &x) {
    x = 0;
    bool sgn = false;
    char c = io::getc();
    for (; c < '0' || '9' < c; c = io::getc()) sgn ^= (c == '-');
    for (; '0' <= c && c <= '9'; c = io::getc()) x = x * 10 + c - '0';
    if (sgn) x = -x;
}
template <typename T>
void write(T x) {
    static char stk[40];
    int tp = 0;
    if (x < 0) {
        io::putc('-');
        x = -x;
    }
    do {
        stk[++tp] = x % 10 + '0';
        x /= 10;
    } while (x);
    while (tp) io::putc(stk[tp--]);
}
using namespace std;
__int128 gcd (__int128 a, __int128 b) {return b ? gcd(b, a % b) : a;}
int T, n, nxt[20], cnt[30];
char s[20];
__int128 pw[20];
vector <char> vec[20];
bool check (vector <char> x, vector <char> y) {
    sort(x.begin(), x.end()), sort(y.begin(), y.end());
    for (int i = 0; i < x.size(); i++) if (x[i] != y[i]) return 0;
    return 1;
}
int main() {
    scanf ("%d", &T);
    bool Flag = (T == 237);
    while (T--) {
        scanf ("%d%s", &n, s + 1);
        int len = strlen(s + 1);
        if (n == 2) {
            __int128 x = 0;
            for (int i = 1; i <= len; i++) x = x * 2 + (s[i] == s[1]);
            write(x), putc('\n');
            continue;
        }
        vector<__int128>val(26,0);
        __int128 cur = 1;
        for (int i = 1; i <= len; i++) {
            val[s[len - i + 1]-'a']+=cur,
            cur*=n;
        }
        vector<__int128>vals;
	    for(auto x:val)if(x!=0)vals.emplace_back(x);
        __int128 x = 0;
        sort(vals.begin(),vals.end());
        for(int i=1;i<vals.size();i++)x=gcd(x,vals[i]-vals[i-1]);
        for(auto y:vals)x=gcd(x,y);
        pw[0] = 1;
        for (int i = 1; i <= len; i++) pw[i] = n * pw[i - 1];
        for (int i = len; i >= 1; i--) if (len % i == 0) {
            for (int j = 0; j < i; j++) vec[j].clear();
            for (int j = 0; j < len; j++) vec[j % i].push_back(s[j + 1]);
            bool flag = 1;
            for (int j = 0; j < i; j++) flag &= check(vec[0], vec[j]);
            if (flag) {
                __int128 y = 0;
                for (int j = 0; j < i; j++) y += pw[j];
                x = x * y / gcd(x, y);
                break;
            }
        }
        for (int i = 1; i <= len; i++) cnt[s[i] - 'a']++;
        int y = 1;
        for (int j = 1; j < n; j++) if ((n - 1) % j == 0) {
            int num = 0, lst = 0;
            for (int i = 0; i < 26; i++) if (cnt[i] && (!lst || cnt[i] % j == lst)) {
                num++;
                lst = cnt[i] % j;
            }
            if (!lst || (num == n && (n * (n - 1) / 2 * lst) % j == 0)) y = y * j / gcd(y, j);
        }
        x = x * y / gcd(x, y);
        y = 1;
        for (int j = 1; j <= n + 1; j++) if ((n + 1) % j == 0) {
            vec[0].clear(), vec[1].clear();
            for (int i = 1; i <= len; i += 2) cnt[s[i] - 'a']++;
            for (int i = 0; i < 26; i++) {
                vec[0].push_back(cnt[i] % j);
                cnt[i] = 0;
            }
            for (int i = 2; i <= len; i += 2) cnt[s[i] - 'a']++;
            for (int i = 0; i < 26; i++) {
                vec[1].push_back(cnt[i] % j);
                cnt[i] = 0;
            }
            bool flag = 1;
            for (int i = 0; i < 26; i++) flag &= (vec[0][i] == vec[1][i]);
            if (flag) y = y * j / gcd(y, j);
        }
        x = x * y / gcd(x, y);
        if (Flag && x == 21) printf ("%d %s\n", n, s + 1);
        write(x), putc('\n');
        for (int i = 0; i < 26; i++) cnt[i] = 0;
    }   
    return io::flush(), 0;
}