#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXL 100000

#define MAXC 26

int v[2*MAXL+10],__next[2*MAXL+10],first[2*MAXL+10],e;

void AddEdge(int U,int V){

    v[++e]=V;

    __next[e]=first[U];

    first[U]=e;

}

char s[MAXL+10];

int len;

struct SAM{

    int endcnt[2*MAXL+10];

    int n,maxlen[2*MAXL+10],minlen[2*MAXL+10],trans[2*MAXL+10][MAXC],slink[2*MAXL+10];

    void clear(){

    	for(int i=0;i<=n;++i){

    		endcnt[i]=maxlen[i]=minlen[i]=slink[i]=first[i]=0;

    		memset(trans[i],0,sizeof(trans[i]));

    	}

    	n=e=0;

    }

    int new_state(int _maxlen,int _minlen,int _trans[],int _slink){

        maxlen[n]=_maxlen;

        minlen[n]=_minlen;

        for(int i=0;i<MAXC;++i){

            if(_trans==NULL){

                trans[n][i]=-1;

            }

            else{

                trans[n][i]=_trans[i];

            }

        }

        slink[n]=_slink;

        return n++;

    }

    int add_char(char ch,int u){

        if(u==-1){

            return new_state(0,0,NULL,-1);

        }

        int c=ch-'a';

        int z=new_state(maxlen[u]+1,-1,NULL,-1);

        endcnt[z]=1;

        int v=u;

        while(v!=-1 && trans[v][c]==-1){

            trans[v][c]=z;

            v=slink[v];

        }

        if(v==-1){

            minlen[z]=1;

            slink[z]=0;

            return z;

        }

        int x=trans[v][c];

        if(maxlen[v]+1==maxlen[x]){

            minlen[z]=maxlen[x]+1;

            slink[z]=x;

            return z;

        }

        int y=new_state(maxlen[v]+1,-1,trans[x],slink[x]);

        slink[y]=slink[x];

        minlen[x]=maxlen[y]+1;

        slink[x]=y;

        minlen[z]=maxlen[y]+1;

        slink[z]=y;

        int w=v;

        while(w!=-1 && trans[w][c]==x){

            trans[w][c]=y;

            w=slink[w];

        }

        minlen[y]=maxlen[slink[y]]+1;

        return z;

    }

    void dfs(int U){

        for(int i=first[U];i;i=__next[i]){

            dfs(v[i]);

            endcnt[U]+=endcnt[v[i]];

        }

    }

    void work_slink_tree(){

        for(int i=1;i<n;++i){

            AddEdge(slink[i],i);

        }

        dfs(0);

    }

}sam;

int anss[MAXL+10];

int T,K;

typedef long long ll;

int main(){

//	freopen("a.in","r",stdin);

	scanf("%d",&T);

	for(;T;--T){

		scanf("%d%s",&K,s);

		len=strlen(s);

   		int U=sam.add_char(0,-1);

    	for(int i=0;i<len;++i){

        	U=sam.add_char(s[i],U);

    	}

    	sam.work_slink_tree();

    	ll ans=0;

    	for(int i=1;i<sam.n;++i){

    		if(sam.endcnt[i]==K){

    			ans+=(ll)(sam.maxlen[i]-sam.minlen[i]+1);

    		}

    	}

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

		sam.clear();

	}

    return 0;

}