#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using pbds =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define cerr if(false)cerr
#define int long long
#define pb push_back
#define F first
#define S second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define yn(x) x ? yes : no
#define f(i, s, e) for (int i = s; i < e; i++)
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int, int>
#define vpi vector<pii>
#define umi unordered_map<int, int>
#define mi map<int, int>
#define si set<int>
#define sc set<char>
#define maxheap priority_queue<int>
#define minheap priority_queue<int, vector<int>, greater<int>>
#define all(x) x.begin(), x.end()
#define minele(x) *min_element(all(x))
#define maxele(x) *max_element(all(x))
#define endl '\n'

const int N = 2e5;
const int m = 1e9 + 7;

#ifndef ONLINE_JUDGE
#define debug(x)            \
    cerr << (#x) << " is "; \
    _print(x)
#define dbg(x) \
    cerr << (#x) << " is " << x << endl;
#else
#define debug(x)
#define dbg(x)
#endif

template <typename T>
void _print(T a)
{
    cerr << a;
}
template <typename T>
void print(T a)
{
    cout << a << ' ';
}
template <typename T>
void println(T a)
{
    cout << a << endl;
}
template <class T>
istream &operator>>(istream &is, vector<T> &a)
{
    for (auto &x : a)
        is >> x;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a)
{
    for (const auto &x : a)
        os << x << ' ';
    return os;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cerr << "{";
    _print(p.F);
    cerr << ",";
    _print(p.S);
    cerr << "} ";
}
template <class T>
void _print(vector<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T>
void _print(set<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T>
void _print(multiset<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T, class V>
void _print(map<T, V> v)
{
    cerr << "[ ";
    for (auto i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T, class V>
void _print(unordered_map<T, V> v)
{
    cerr << "[ ";
    for (auto i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}

/////////////Sieve///////////////
// vb sieve(N + 5, true);
// vi primes;
// void gensieve()
// {
//     sieve[0] = sieve[1] = false;
//     for (int i = 2; i <= sqrt(N); i++)
//     {
//         if (sieve[i])
//         {
//             for (int j = i * i; j <= N; j += i)
//                 sieve[j] = false;
//         }
//     }
//     for (int i = 2; i <= N; i++)
//     {
//         if (sieve[i])
//             primes.pb(i);
//     }
// }
////////////////////////////////

int binpow(int a, int b)
{
    int ans = 1;
    a %= m;
    while (b)
    {
        if (b & 1)
            ans = ((ans % m) * (a % m)) % m;

        a = ((a % m) * (a % m)) % m;
        b >>= 1;
    }
    return ans;
}

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void init_code()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif // ONLINE_JUDGE
}

const int p = 31;
vector<int> powers(N);

int add(int a, int b)
{
    a %= m;
    b %= m;

    return (a + b) % m;
}

int mul(int a, int b)
{
    a %= m;
    b %= m;

    return (a * b) % m;
}

int sub(int a, int b)
{
    a %= m;
    b %= m;

    return (a - b + m) % m;
}

void powercmp()
{
    int x = 1;
    for (int i = 0; i < N; i++)
    {
        powers[i] = x % m;
        x = mul(x, p);
    }
}

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int x = 0;
    int e = 0;

    for(auto i : s)
    {
        x = add(x, mul(i - 'a' + 1, powers[e++]));
    }

    int ogx = x;

    si st;
    f(i, 0, n - 2)
    {
        x = sub(x, mul((s[i] - 'a' + 1), powers[i]));
        x = sub(x, mul((s[i + 1] - 'a' + 1), powers[i + 1]));
        x = sub(x, mul((s[i + 2] - 'a' + 1), powers[i + 2]));

        x = add(x, mul((s[i + 1] - 'a' + 1), powers[i]));
        x = add(x, mul((s[i + 2] - 'a' + 1), powers[i + 1]));
        x = add(x, mul((s[i] - 'a' + 1), powers[i + 2]));


        st.insert(x);
        x = ogx;
    }
    println(st.size());
}

signed main()
{
    init_code();
    fast();
    int t = 1;
    cin >> t;
    powercmp();
    while (t--)
    {
        solve();
    }
    return 0;
}