#include <iostream>
#include <cmath>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef unsigned long long ull;

const int PRIME_CONST = 29;
const ull MAX_SIZE = INT_MAX;

ull scratch_hash(string s) {
    ull hash = 0;
    for (short i = 0; i < s.length(); i++) {
       hash = (PRIME_CONST * hash + s[i]) % MAX_SIZE;
    }
    return hash;
}

int ground_truth(string latin, int len) {
    hash<string> hasher;
    unordered_set<size_t> mp;
    for (short i = 0; i < len - 1; i += 1) {
        string removed = latin.substr(0, i) + latin.substr(i + 2, len - 1);
        mp.insert(hasher(removed));
    }
    return mp.size();
}

void solve() {
    int len;
    string latin;
    cin >> len >> latin;

    unordered_set<ull> mp;
    ull prefix_hash = 0;
    ull postfix_hash = 0;
    ull old_bit_base = 1;

    for (int i = 0; i < len - 3; i += 1) {
        old_bit_base = (old_bit_base * PRIME_CONST) % MAX_SIZE;
    }


    for (short i = 2; i < len; i += 1) {
        postfix_hash = (postfix_hash * PRIME_CONST + latin[i]) % MAX_SIZE;
    }

    ull hash;
    for (short i = 0; i < len - 1; i += 1) {
        string prefix_string = latin.substr(0, i);
        string postfix_string = latin.substr(i + 2, len - 1);
        string removed = prefix_string + postfix_string;

        hash = (prefix_hash + postfix_hash) % MAX_SIZE;

        cout << "On string: " << removed << " hash " << hash << " expected " << scratch_hash(removed) << endl;
        cout << "Prefix : " << prefix_hash << " Postfix: " << postfix_hash << endl;
        mp.insert(hash);
        prefix_hash = (prefix_hash + latin[i] * old_bit_base) % MAX_SIZE;
        postfix_hash = (postfix_hash - latin[i+2] * old_bit_base) % MAX_SIZE;
        old_bit_base = (old_bit_base / PRIME_CONST) % MAX_SIZE;
    }
    cout << mp.size() << endl;
}

int main() {
    int n = 0;
    cin >> n;
    while (n--) {
        solve();
    }
    return 0;
}