temp

#include<bits/stdc++.h>
using namespace std;
const int MX=200003;
int t,rk[MX],v_rk[MX],sx[MX],v_sx[MX],lcp[MX],v_lcp[MX],vv[MX],st[30][MX],re[30][MX];
string q,w;
void process_occur()
{
    int g,h,x;
    for(g=0;g<26;g++){
        x=q[0]-'a';
        st[g][0]=(x==g)?1:0;
        re[g][0]=0;
        for(h=1;q[h];h++){
            x=q[h]-'a';
            st[g][h]=st[g][h-1]+((x==g)?1:0);
            re[g][h]=0;
        }
    }
}
void process_suffix(int z)
{
    int g,re,x,xx;
    int nt[MX]={0};
    xx=max(t,300);
    for(g=0;g<q.length();g++)
        if(g+z<q.length()) nt[rk[g+z]]++;
        else nt[0]++;
    for(g=re=0;g<xx;g++)
        x=nt[g], nt[g]=re, re+=x;
    for(g=0;g<q.length();g++)
        if(sx[g]+z<q.length()) v_sx[nt[rk[sx[g]+z]]++]=sx[g];
        else v_sx[nt[0]++]=sx[g];
    for(g=0;g<q.length();g++)
        sx[g]=v_sx[g];
}
void create_suffix()
{
    int g,h,r;
    for(g=0;g<q.length();g++)sx[g]=g, rk[g]=q[g];
    for(g=1;g<q.length();g<<=1){
        process_suffix(g);
        process_suffix(0);
        v_rk[sx[0]]=r=0;
        for(h=1;h<q.length();h++)
            if(rk[sx[h]]==rk[sx[h-1]]&&rk[sx[h]+g]==rk[sx[h-1]+g])
                v_rk[sx[h]]=r;
            else v_rk[sx[h]]= ++r;
        for(h=0;h<q.length();h++)
            rk[h]=v_rk[h];
        if(rk[sx[q.length()-1]]==q.length()-1)break;
    }
}
//LCP
void longest_same_prefix()
{
    int g,lo;
    vv[sx[0]]=-1;
    for(g=1;g<t;g++) vv[sx[g]]=sx[g-1];
    for(g=lo=0;g<t;g++){
        if(vv[g]==-1){
            v_lcp[g]=0;
            continue;
        }
        while(q[g+lo]==q[vv[g]+lo])lo++;
        v_lcp[g]=lo;
        lo=max(0,lo-1);
    }
    for(g=0;g<t;g++)
        lcp[g]=v_lcp[sx[g]];
}
//Root Check
int root(int z)
{
    return z<(t-w.length()-1)?1:2;
}
void process_result()
{
    int g,h,x,lo,hi,nt;
    for(g=0;g<26;g++){
        for(h=1;h<t;h++){
            x=q[sx[h]]-'a';
            if(x==g&&root(sx[h])!=root(sx[h-1])){
                hi=sx[h]+lcp[h]-1;
                lo=sx[h]-1;
                nt=st[g][hi]-((lo-1)<0?0:st[g][lo-1]);
                re[g][nt]++;
            }
        }
    }
}
void printall()
{
    int g;
    for(g=0;g<t;g++){
        printf("%d\t%d\t%d\t%s\n",sx[g],root(sx[g]),lcp[g],q.c_str()+sx[g]);
    }
}
int main()
{
    int g,ts,tm,y,x,s=1;
    string a;
    scanf("%d",&ts);
    while(ts--){
        cin>>tm>>q;
        process_occur();
        w=q;
        reverse(w.begin(),w.end());
        q+=w, q+="$";
        t=q.size();
        create_suffix();
        longest_same_prefix();
        process_result();
        printall();
        printf("Case %d:\n",s++);
        cin>>y>>a;
        for(g=0;g<y;g++){
            scanf("%d",&x);
            printf("%d\n",(x>(int)1e5)?0:re[(a[g]-'a')][x]);
        }
    }
    return 0;
}