Spring-songman

#include <bits/stdc++.h>

using namespace std;
using LINT = long long int;
using PII = pair<int,int>;

#define PB push_back
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)

int n,k;
string s;

LINT LEMOD=1000000007;
LINT ALPH=31;
LINT ALPH2=49;

void process(){
    cin>>n>>k>>s;s+='$';
    unordered_map<int,unordered_set<int>> hashmap;
    LINT hash=0;
    LINT hash2=0;
    REP(i,k){
        hash = (hash*ALPH+s[i]-'a') % LEMOD;
        hash2 = (hash2*ALPH2+s[i]-'a') % LEMOD;
    }

    LINT ALPHK = 1;
    LINT ALPH2K = 1;
    REP(i,k-1){
        ALPHK = ALPHK*ALPH%LEMOD;
        ALPH2K = ALPH2K*ALPH2%LEMOD;
    }

    REP(i,n-k+1){
        hashmap[hash].insert(hash2);
        hash = ((hash-ALPHK*(s[i]-'a')+2*LEMOD)%LEMOD*ALPH+s[i+k]-'a')%LEMOD;
        hash2 = ((hash2-ALPH2K*(s[i]-'a')+2*LEMOD)%LEMOD*ALPH2+s[i+k]-'a')%LEMOD;
    }

    int cnt = 0;
    for(auto & p : hashmap)
        cnt += p.SE.size();
    cout<<cnt<<endl;
}

int main() {
    int t;cin>>t;
    while(t--)process();
    return 0;
}