Spring

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX (1<<19)
typedef unsigned char uc;
uc M[]={128,64,32,16,8,4,2,1};
#define SI (sizeof(int))
#define tg(i) ((t[(i)>>3]&M[(i)&7])?1:0)
#define ts(i, b) t[(i)>>3]=(b) ? (M[(i)&7]|t[(i)>>3]):((~M[(i)&7])&t[(i)>>3])
#define chr(i) (cs==SI?((int*)s)[i]:((uc*)s)[i])
#define lms(i) (i>0&&tg(i)&&!tg(i-1))
void buc(uc *s,int *b,int n,int K,int cs,bool e){
    int S(0);
    F(K+1)b[i]=0;
    F(n)++b[chr(i)];
    F(K+1)S+=b[i],b[i]=e?S:S-b[i];
}
void isa(uc*t,int*SA,uc*s,int*b,int n,int K,int cs,bool e){
    int j;
    buc(s,b,n,K,cs,e);
    F(n)if((j=SA[i]-1)>=0&&!tg(j))
        SA[b[chr(j)]++]=j;
}
void sas(uc*t,int*SA,uc*s,int*b,int n,int K,int cs,bool e){
    int j;
    buc(s,b,n,K,cs,e);
    for(int i(n-1);~i;--i)
        if((j=SA[i]-1)>=0&&tg(j))
            SA[--b[chr(j)]]=j;
}
void sa(uc*s,int*SA,int n,int K=256,int cs=1){
    static int b[MX];
    int j,n1(0),h(0),w(-1),p,f;
    uc *t=(uc*)malloc(n>>3|1);
    ts(n-2,0),ts(n-1,1);
    for(int i(n-3);~i;--i)
        ts(i,(chr(i)<chr(i+1)||(chr(i)==chr(i+1)&&tg(i+1)==1))?1:0);
    buc(s,b,n,K,cs,1);
    F(n)SA[i] = -1;
    FT(1,n)if(lms(k))SA[--b[chr(k)]]=k;
    isa(t,SA,s,b,n,K,cs,0);
    sas(t,SA,s,b,n,K,cs,1);
    F(n)if(lms(SA[i]))SA[n1++]=SA[i];
    FT(n1,n)SA[k]=-1;
    F(n1){
        p=SA[i],f=0;
        F(n)if(!~w||chr(p+i)!=chr(w+i)||tg(p+i)!=tg(w+i))f=1,i=n;
            else if(i>0&&(lms(p+i)||lms(w+i)))break;
        if(f)++h,w=p;
        p>>=1,SA[n1+p]=h-1;
    }
    for(int i(n-1),j(n-1);i>=n1;--i)
        if(SA[i]>=0)SA[j--]=SA[i];
    int *SA1=SA,*s1=SA+n-n1;
    if(h<n1)sa((uc*)s1,SA1,n1,h-1,SI);
    else F(n1)SA1[s1[i]]=i;
    buc(s,b,n,K,cs,1);
    j=0;FT(1,n)if(lms(k))s1[j++]=k;
    F(n1)SA1[i]=s1[SA1[i]];
    FT(n1,n)SA[k]=-1;
    for(int i(n1-1);~i;--i)
        j=SA[i],SA[i]=-1,SA[--b[chr(j)]]=j;
    isa(t,SA,s,b,n,K,cs,0),sas(t,SA,s,b,n,K,cs,1);
    free(t);
}
void lcp(int *sa,int *lcp,int n,uc *s){
    static int r[MX];
    F(n)r[sa[i]]=i,lcp[i]=0;;
    int h(0);F(n)if(r[i]<n-1){
        for(int j(sa[r[i]+1]);s[i+h]==s[j+h];++h);
        lcp[r[i]]=h;
        if(h)--h;
    }
}
uc s[MX];
int N,K,O,C[MX],SA[MX],S;
int main(void){
    IN(tt)F(tt){
        assert(scanf("%d%d%s",&N,&K,s)==3),assert(K<=N&&K>=0&&N<=1e5),O+=N;
        sa(s,SA,N+1),lcp(SA,C,N+1,s),S=0;
        F(N+1)S+=SA[i]<=N-K&&C[i]<K;
        printf("%d\n",S);
    }
    assert(O<=3e5);
    return 0;
}