#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
int child[4][4];
int cnt;
} trie[2000005];
unordered_map<char,int> mp={{'A',0},{'G',1},{'C',2},{'U',3}};
char rna[4]={'A','G','C','U'};
string p,q,s[2000005];
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=mp[s[i]];
int c2=mp[s[n-i-1]];
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[mp[p[k+1]]][mp[rna[i]]]!=-1)
ret+=dfs1(trie[u].child[mp[p[k+1]]][mp[rna[i]]],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[mp[rna[i]]][mp[q[b-k-2]]]!=-1)
ret+=dfs2(trie[u].child[mp[rna[i]]][mp[q[b-k-2]]],k+1);
}
return ret;
}
int solve(){
int cur=0;
for(int i=0; i<min(a,b); i++){
int c1=mp[p[i]];
int c2=mp[q[b-i-1]];
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;
}
