#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e6+5;
const int base=31;
const ll MOD=1e9+7;
int n,m,cur=0,cur1=0;
vector<string> S;
// ACGU
char a[]={'A','C','G','U'};
struct Node
{
int child[4];
int l,r;
vector<int> id;
};
Node nodes[maxn],nodes1[maxn];
int new_node()
{
cur++;
memset(nodes[cur].child,-1,sizeof(nodes[cur].child));
return cur;
}
int new_node1()
{
cur1++;
memset(nodes1[cur1].child,-1,sizeof(nodes1[cur1].child));
return cur1;
}
void add_string(string s,int idx)
{
int pos=0;
for(int i=0;i<s.size();i++){
int c=0;
for(int x=0;x<4;x++){
if(s[i]==a[x]) c=x;
}
if(nodes[pos].child[c]==-1){
nodes[pos].child[c]=new_node();
}
pos=nodes[pos].child[c];
if(nodes[pos].l==0) nodes[pos].l=idx;
nodes[pos].r=idx;
}
}
void add_string1(string s,int idx)
{
int pos=0;
for(int i=0;i<s.size();i++){
int c=0;
for(int x=0;x<4;x++){
if(s[i]==a[x]) c=x;
}
if(nodes1[pos].child[c]==-1){
nodes1[pos].child[c]=new_node1();
}
pos=nodes1[pos].child[c];
nodes1[pos].id.push_back(idx);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
memset(nodes[0].child,-1,sizeof(nodes[0].child));
memset(nodes1[0].child,-1,sizeof(nodes1[0].child));
cin>>n>>m;
for(int i=1;i<=n;i++){
string x;
cin>>x;
S.push_back(x);
}
sort(S.begin(),S.end());
for(int i=0;i<S.size();i++){
add_string(S[i],i+1);
reverse(S[i].begin(),S[i].end());
add_string1(S[i],i+1);
}
while(m--){
string p,q;
cin>>p>>q;
int pos=0,ans=0;
bool check=true;
for(int i=0;i<p.size();i++){
int c=0;
for(int x=0;x<4;x++){
if(p[i]==a[x]) c=x;
}
if(nodes[pos].child[c]==-1){
check=false;
break;
}
pos=nodes[pos].child[c];
}
if(check){
int L=nodes[pos].l;
int R=nodes[pos].r;
pos=0;
reverse(q.begin(),q.end());
for(int i=0;i<q.size();i++){
int c=0;
for(int x=0;x<4;x++){
if(q[i]==a[x]) c=x;
}
if(nodes1[pos].child[c]==-1) check=false;
pos=nodes1[pos].child[c];
}
if(!check) cout<<0<<'\n';
else{
int ans=0;
int l=lower_bound(nodes1[pos].id.begin(),nodes1[pos].id.end(),L)-nodes1[pos].id.begin();
int r=upper_bound(nodes1[pos].id.begin(),nodes1[pos].id.end(),R)-nodes1[pos].id.begin()-1;
cout<<max(0,r-l+1)<<'\n';
}
}
else cout<<0<<'\n';
}
}
