#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;
#define i128 __int128
i128 gcd (i128 a, i128 b) {return b ? gcd(b, a % b) : a;}
int T, n, mp[30];
char s[20];
i128 pw[20], val[30];
int main() {
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%s", &n, s + 1);
        int len = strlen(s + 1);
        if (n == 2) {
            i128 x = 0;
            for (int i = 1; i <= len; i++) x = x * 2 + (s[i] == s[1]);
            write(x), putc('\n');
            continue;
        }
        pw[0] = 1;
        for (int i = 1; i <= len; i++) pw[i] = n * pw[i - 1];
        for (int i = 0; i < 26; i++) val[i] = 0;
        for (int i = 1; i <= len; i++) val[s[i] - 'a'] += pw[len - i];
        sort(val, val + 26);
        int cnt = 0;
        i128 ans = 0;
        for (int i = 0; i < 26; i++) if (val[i]) cnt++;
        if (cnt != n) {
            for (int i = 0; i < 26; i++) if (val[i]) ans = gcd(ans, val[i]);
        } else {
            for (int i = 0; i < 26; i++) mp[i] = 0;
            for (int i = 1, j = 0; i <= len; i++) {
                if (!mp[s[i] - 'a']) mp[s[i] - 'a'] = j++;
                ans = ans * n + mp[s[i] - 'a'];
            }
            for (int i = 0; i < 25; i++) if (val[i]) ans = gcd(ans, val[i + 1] - val[i]);
        }
        write(ans), putc('\n');
    }
    return io::flush(), 0;
}