#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#define ll long long
// #define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+100;
const int M=3e5+100;
const int B=447;
const int mod=998244353;
const ll INF=1e18;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
int shrink(char x){
if(x=='A')return 0;
if(x=='G')return 1;
if(x=='C')return 2;
if(x=='U')return 3;
return 5;
}
struct node{
node *to[4];
vector<int>val;
};
node ram[3000000];int point=0;
node *alloc(){
node *res=&(ram[point++]);
for(int j=0;j<4;j++){
res->to[j]=nullptr;
}
return res;
}
int n,m;
string s[N],p[N],q[N];
node *trie,*trie_rev;
int px[N],py[N],lx[N],rx[N],ly[N],ry[N];
void append(node *cur,string &x,int pos){
for(int i=0;i<x.size();i++){
int c=x[i];
if(!cur->to[c]){
cur->to[c]=alloc();
}
cur=cur->to[c];
}
cur->val.push_back(pos);
}
void dfs(node *cur,int *tin,int *pr,int *l,int *r){
if(cur==nullptr)return;
for(auto i:cur->val){
if(i<0){
l[-i]=*tin;
}
}
for(auto i:cur->val){
if(i>0){
pr[i]=(*tin)++;
}
}
for(int i=0;i<4;i++){
dfs(cur->to[i],tin,pr,l,r);
}
for(auto i:cur->val){
if(i<0){
r[-i]=*tin;
}
}
}
struct query{
int pos,type,tl,tr;
query(int pos=0,int type=0,int tl=0,int tr=0) : pos(pos),type(type),tl(tl),tr(tr){}
};
bool operator<(const query &x,const query &y){
if(x.pos==y.pos){
return x.type<y.type;
}
return x.pos<y.pos;
}
int ans[N];
int f[M];
void upd(int r,int y){
++r;
for(;r<M;r+=((-r)&r)){
f[r]+=y;
}
}
int calc(int r){
int res=0;
++r;
for(;r>0;r-=((-r)&r)){
res+=f[r];
}
return res;
}
int calc(int l,int r){
return calc(r-1)-calc(l-1);
}
void test(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(auto &j:s[i]){
j=shrink(j);
}
}
for(int i=1;i<=m;i++){
cin>>p[i];
for(auto &j:p[i]){
j=shrink(j);
}
cin>>q[i];
for(auto &j:q[i]){
j=shrink(j);
}
}
trie=alloc();
trie_rev=alloc();
for(int i=1;i<=n;i++){
append(trie,s[i],i);
reverse(s[i].begin(),s[i].end());
append(trie_rev,s[i],i);
}
for(int i=1;i<=m;i++){
append(trie,p[i],-i);
reverse(q[i].begin(),q[i].end());
append(trie_rev,q[i],-i);
}
int tin=0;
dfs(trie,&tin,px,lx,rx);
tin=0;
dfs(trie_rev,&tin,py,ly,ry);
for(int i=1;i<=m;i++){
ans[i]=0;
}
vector<query>v;
for(int i=1;i<=n;i++){
v.push_back(query(px[i],1e9,py[i]));
// cout<<px[i]<<' '<<py[i]<<'\n';
}
for(int i=1;i<=m;i++){
v.push_back(query(lx[i],-i,ly[i],ry[i]));
v.push_back(query(rx[i],i,ly[i],ry[i]));
// cout<<lx[i]<<' '<<rx[i]<<' '<<ly[i]<<' '<<ry[i]<<'\n';
}
// return;
sort(v.begin(),v.end());
for(query&i:v){
if(i.type==1e9){
upd(i.tl,1);
continue;
}
if(i.type>0){
ans[i.type]+=calc(i.tl,i.tr);
}
else{
ans[-i.type]-=calc(i.tl,i.tr);
}
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<'\n';
}
}
/*
*/
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// cout.tie(nullptr);
int t2=1;
// cin>>t2;
for(int i=1;i<=t2;i++){
test();
}
}
