#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 2e5+5;
struct seg{int ls,rs,sz;}t[N*40];
int n,q,tot=1,last=1,tr[N][10],fa[N],len[N],rt[N],Node,tong[N],a[N];
char s[N];
void extend(int c){
    int v=last,u=++tot;last=u;
    len[u]=len[v]+1;
    while (v&&!tr[v][c]) tr[v][c]=u,v=fa[v];
    if (!v) fa[u]=1;
    else{
        int x=tr[v][c];
        if (len[x]==len[v]+1) fa[u]=x;
        else{
            int y=++tot;
            memcpy(tr[y],tr[x],sizeof(tr[y]));
            fa[y]=fa[x];fa[x]=fa[u]=y;len[y]=len[v]+1;
            while (v&&tr[v][c]==x) tr[v][c]=y,v=fa[v];
        }
    }
}
void modify(int &x,int l,int r,int p){
    if (!x) x=++Node;++t[x].sz;
    if (l==r) return;int mid=l+r>>1;
    if (p<=mid) modify(t[x].ls,l,mid,p);
    else modify(t[x].rs,mid+1,r,p);
}
int merge(int x,int y){
    if (!x||!y) return x|y;
    int z=++Node;t[z].sz=t[x].sz+t[y].sz;
    t[z].ls=merge(t[x].ls,t[y].ls);
    t[z].rs=merge(t[x].rs,t[y].rs);
    return z;
}
int find(int x,int l,int r){
    if (l==r) return l;int mid=l+r>>1;
    if (t[t[x].ls].sz) return find(t[x].ls,l,mid);
    else return find(t[x].rs,mid+1,r);
}
int query(int x,int l,int r,int ql,int qr){
    if (l>=ql&&r<=qr) return t[x].sz;
    int mid=l+r>>1,res=0;
    if (ql<=mid) res+=query(t[x].ls,l,mid,ql,qr);
    if (qr>mid) res+=query(t[x].rs,mid+1,r,ql,qr);
    return res;
}
int main(){
    n=gi();scanf("%s",s+1);
    for (int i=1;i<=n;++i) extend(s[i]-'0'),modify(rt[last],1,n,i);
    for (int i=1;i<=tot;++i) ++tong[len[i]];
    for (int i=1;i<=n;++i) tong[i]+=tong[i-1];
    for (int i=1;i<=tot;++i) a[tong[len[i]]--]=i;
    for (int i=tot;i>1;--i) rt[fa[a[i]]]=merge(rt[fa[a[i]]],rt[a[i]]);
    q=gi();while (q--){
        scanf("%s",s+1);int l=strlen(s+1),now=1,lst;
        long long ans=0;
        for (int i=1;i<=l;++i) now=tr[now][s[i]-'0'];
        if (now) lst=find(rt[now],1,n),ans=lst-l;
        else lst=-1,ans=n;
        now=1;
        for (int i=1;i<=l;++i){
            now=tr[now][s[i]-'0'];
            if (now) ans+=query(rt[now],1,n,1,lst==-1?n:lst-l+i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}