#include <iostream>
#include <fstream>
#define MAX 100010

using namespace std;

int lp,ls,n,nra;
char c;

bool a[MAX],b[MAX];
int lps[MAX];

void calc_lps(bool pat[MAX],int lps[MAX]){
  lps[0]=0;
  int la=0;
  for(int i=1;i<lp;)
    if(pat[i]==pat[la])lps[i++]=++la;
    else
      if(la!=0)la=lps[la-1];
      else lps[i++]=0;
}
void rez(bool st[MAX],bool pat[MAX]){
  calc_lps(pat,lps);
  for(int i=0,j=0;i<ls;){
    if(st[i]==pat[j])i++,j++;
    if(j==lp){
      nra++;
      j=lps[j-1];
    } else if(i<ls&&st[i]!=pat[j]){
      if(j!=0)j=lps[j-1];
      else i++;
    }
  }
}

int main()
{
    ifstream f ("virus.in");
    ofstream g ("virus.out");
    f>>ls>>n;
    for(int i=0;i<ls;i++)
      f>>c,
      a[i]=(c-'0');
    for(int i=1;i<=n;i++){
      f>>lp;
      for(int i=0;i<lp;i++)
        f>>c,
        b[i]=(c-'0');
      nra=0; rez(a,b);
      g<<nra<<'\n';
    }
    return 0;
}