#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>//常用的头文件。不知道有什么用的可以百度。
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=16000010;
typedef __int64 ll;
char txt[maxn],tp;
map<string,int> mp;//建立map映射
int main()
{
    int i,j,n,nc,t,len,ans,one=1;

    scanf("%d",&t);
    while(t--)
    {
        if(!one)//判断是否是第一个输入。因为样例之间要空一行。
            printf("\n");
        scanf("%d%d",&n,&nc);
        scanf("%s",txt);
        len=strlen(txt);
        ans=0;
        mp.clear();//全部清0
        for(j=n;j<=len;j++)
        {
            tp=txt[j];
            txt[j]=‘\0‘;
            string tt(txt+j-n);//取出字符串.其实可以string tt(txt+j-n,n)。比赛时忘了
            txt[j]=tp;
            if(!mp[tt])
                ans++,mp[tt]=1;
        }
        printf("%d\n",ans);
        one=0;
    }
    return 0;
}

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>//常用的头文件。不知道有什么用的可以百度。
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=16000010;
const int maxm=8000007;
const int mod=1000007;
typedef __int64 ll;
char txt[maxn],tp;
int nc;
int Hash[maxm],id[28];
int getkey(int st,int len)//获取hash值
{
    int i,key=0;
    for(i=0;i<len;i++)
        key=key*nc+id[txt[st+i]-‘a‘];
    return key;
}
int main()
{
    int i,n,t,tp,len,ans,key,cnt;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&nc);
        scanf("%s",txt);
        memset(Hash,0,sizeof Hash);
        memset(id,-1,sizeof id);
        ans=cnt=0;
        len=strlen(txt);
        for(i=0;i<len;i++)
        {
            tp=txt[i]-‘a‘;
            if(id[tp]==-1)
                id[tp]=cnt++;//压缩字母的数值
            if(cnt==nc)
                break;
        }
        for(i=n;i<=len;i++)
        {
            key=getkey(i-n,n);
            key%=maxn;
            if(!Hash[key])
                ans++,Hash[key]=1;
        }
        printf("%d\n",ans);
        if(t)//判断是否是第一个输入。因为样例之间要空一行。
            printf("\n");
    }
    return 0;
}