/*

    这道题用到一个常用的技巧（虽然我这是第一次见）。

    枚举U的长度，然后每隔U枚举i，然后确定j，则j一定在另一个U里面，有了i、j之后，向左向右扩展，看看能匹配多长。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 600010

using namespace std;

int t1[N],t2[N],c[N],s[N],sa[N],rk[N],height[N],n;

int st[N][],lg2[N];

char ch[N];

bool cmp(int *y,int a,int b,int k){

    int a1=y[a],b1=y[b];

    int a2=a+k<=n?y[a+k]:-;

    int b2=b+k<=n?y[b+k]:-;

    return a1==b1&&a2==b2;

}

void DA(){

    int *x=t1,*y=t2,m=;

    for(int i=;i<=m;i++) c[i]=;

    for(int i=;i<=n;i++) c[x[i]=s[i]]++;

    for(int i=;i<=m;i++) c[i]+=c[i-];

    for(int i=n;i;i--) sa[c[x[i]]--]=i;

    for(int k=,p=;k<=n;k*=,m=p,p=){

        for(int i=n-k+;i<=n;i++) y[++p]=i;

        for(int i=;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;

        for(int i=;i<=m;i++) c[i]=;

        for(int i=;i<=n;i++) c[x[y[i]]]++;

        for(int i=;i<=m;i++) c[i]+=c[i-];

        for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];

        swap(x,y);p=;x[sa[]]=;

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

            if(cmp(y,sa[i-],sa[i],k)) x[sa[i]]=p;

            else x[sa[i]]=++p;

        if(p>=n) break;

    }

}

void geth(){

    for(int i=;i<=n;i++) rk[sa[i]]=i;

    for(int i=,j=;i<=n;i++){

        while(s[i+j]==s[sa[rk[i]-]+j]) j++;

        height[rk[i]]=j;

        if(j) j--;

    }

    for(int i=;i<=n;i++) lg2[i]=lg2[i>>]+;

    for(int i=;i<=n;i++) st[i][]=height[i];

    for(int j=;(<<j)<=n;j++)

        for(int i=;i+(<<j)-<=n;i++)

            st[i][j]=min(st[i][j-],st[i+(<<j-)][j-]);

}

int query(int l,int r){

    l=rk[l];r=rk[r];

    if(l>r) swap(l,r);

    int k=lg2[r-l];

    return min(st[l+][k],st[r-(<<k)+][k]);

}

int main(){

    int T;scanf("%d",&T);

    for(int cas=;cas<=T;cas++){

        long long ans=;int G;

        scanf("%d%s",&G,ch+);

        int len=strlen(ch+);

        for(int i=;i<=len;i++) s[i]=s[len*-i+]=ch[i]-'a'+;

        s[len+]=;n=len*+;

        DA();geth();

        for(int U=;U*+G<=len;U++)

            for(int i=;i+U+G<=len;i+=U){

                int j=i+U+G;

                if(s[i]!=s[j]) continue;

                int L=min(U,query(i,j))+min(U,query(len*-i+,len*-j+))-;//分别为向右和向左扩展

                if(L>=U) ans+=L-U+;

            }

        cout<<"Case "<<cas<<": "<<ans<<endl;

    }

    return ;

}