#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
int child[30][30];
int cnt;
} trie[100005];
char rna[4]={'A','G','C','U'};
string p,q,s[100005];
int nnode,n,m,a,b;
int new_node(){
nnode++;
memset(trie[nnode].child, -1, sizeof trie[nnode].child);
trie[nnode].cnt=0;
return nnode;
}
void ins(string s){
int cur=0;
int n=s.size();
for(int i=0; i<n; i++){
int c1=s[i]-'A';
int c2=s[n-i-1]-'A';
if(trie[cur].child[c1][c2]==-1) trie[cur].child[c1][c2]=new_node();
cur=trie[cur].child[c1][c2];
trie[cur].cnt++;
}
}
int dfs1(int u, int k){
int ret=0;
if(k==a-1) return trie[u].cnt;
for(int i=0; i<4; i++){
if(trie[u].child[p[k+1]-'A'][rna[i]-'A']!=-1)
ret+=dfs1(trie[u].child[p[k+1]-'A'][rna[i]-'A'],k+1);
}
return ret;
}
int dfs2(int u, int k){
int ret=0;
if(k==b-1) return trie[u].cnt;
for(int i=0; i<4; i++){
if(trie[u].child[rna[i]-'A'][q[b-k-2]-'A']!=-1)
ret+=dfs2(trie[u].child[rna[i]-'A'][q[b-k-2]-'A'],k+1);
}
return ret;
}
int solve(){
int cur=0;
for(int i=0; i<min(a,b); i++){
int c1=p[i]-'A';
int c2=q[b-i-1]-'A';
if(trie[cur].child[c1][c2]==-1) return 0;
cur=trie[cur].child[c1][c2];
}
if(a>b){
int tmp=dfs1(cur,b-1);
return tmp;
}
if(a<b){
int tmp=dfs2(cur,a-1);
return tmp;
}
return trie[cur].cnt;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
memset(trie[0].child, -1, sizeof(trie[0].child));
trie[0].cnt=0;
for(int i=1; i<=n; i++){
cin>>s[i];
ins(s[i]);
}
while(m--){
cin>>p>>q;
a=p.size(),b=q.size();
cout<<solve()<<'\n';
}
return 0;
}
