#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;
int T, n, nxt[20], cnt[30];
char s[20];
__int128 pw[20];
int main() {
    scanf ("%d", &T);
    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;
        }
        for (int i = 2, j = 0; i <= len; i++) {
            while (j && s[j + 1] != s[i]) j = nxt[j];
            if (s[j + 1] == s[i]) j++;
            nxt[i] = j;
        }
        pw[0] = 1;
        for (int i = 1; i <= len; i++) pw[i] = n * pw[i - 1];
        __int128 x = 0;
        if (len % (len - nxt[len]) == 0) {
            for (int i = 0; i < len / (len - nxt[len]); i++) x += pw[i * (len - nxt[len])];
        } else x = 1;
        for (int i = 1; i <= len; i++) cnt[s[i] - 'a']++;
        int num = 0, sum = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i]) num++;
            if (cnt[i] % (n - 1) == 1) sum++;
        }
        if (sum == n) x *= n - 1;
        write(x), putc('\n');
        for (int i = 0; i < 26; i++) cnt[i] = 0;
    }   
    return io::flush(), 0;
}