//412_4
#include <iostream>
#include <algorithm>
#include <stdio.h>

#define link ololink
using namespace std;

const int N = 2e5+5;
int len[N], link[N], to[N][4];
bool u[N];
char s[N];

int f(char c){
    if(c=='A') return 0;
    if(c=='C') return 1;
    if(c=='G') return 2;
    if(c=='T') return 3;
    return -1;
}

int main()
{
    freopen("DEBRUIJN.IN","r", stdin);
    //freopen("input.txt", "r", stdin);


    int tt;
    scanf("%d", &tt);
    while(tt--){
        int K;
        scanf("%d%s",&K,&s);
        int n = strlen(s);
        int l = 0, d = 1;
        link[l] = -1;
        len[l] = 0;
        memset(to[l], 0, sizeof(to[l]));



        for(int i=0;i<n;++i){
            int x = d++;
            int c = f(s[i]);

            len[x] = len[l]  + 1;
            link[x] = 0;
            memset(to[x], 0, sizeof(to[x]));
            for(; l!=-1 && !to[l][c]; l=link[l]) to[l][c] = x;
            if(~l){
                int p = to[l][c];
                if(len[p]==len[l]+1) link[x] = p; else{
                    int q = d++;
                    len[q] = len[l]+1;
                    link[q] = link[p];
                    memcpy(to[q], to[p], sizeof(to[q]));
                    for(; l!=-1 && to[l][c]==p; l=link[l]) to[l][c] = q;
                    link[p] = link[x] = q;
                }
            }
            l=x;
        }


        for(int i=0;i<d;++i) u[i] = 0;

        int v  =0;
        for(int i=0;i<K-1;++i){
            v = to[v][f(s[i])];
        }



        for(int i=K-1;i<n;++i){
            v = to[v][f(s[i])];
            while(v && len[link[v]]>=K) v = link[v];
            u[v] = 1;
        }

        int ans = 0;
        for(int i=0;i<d;++i) if(u[i]){
            int deg = 0;
            for(int c=0;c<4;++c) if(to[i][c]) ++deg;
            if(deg>1) ++ans;
        }

        printf("%d\n",ans);
    }

    return 0;
}

