#include <bits/stdc++.h>
using namespace std;
int getNum(char f) {
if(f=='A') return 0;
if(f=='U') return 1;
if(f=='G') return 2;
return 3;
}
struct Trie {
struct node{
node* child[4][4];
int cnt;
node() {
for(int i=0;i<4;i++) for(int j=0;j<4;j++) child[i][j]=NULL;
cnt=0;
}
};
node* root;
Trie() {
root=new node();
}
void add(string s) {
node* u=root;
int n=s.size();
for(int i=0;i<n;i++) {
int c1=getNum(s[i]),c2=getNum(s[n-i-1]);
if(u->child[c1][c2]==NULL) u->child[c1][c2]=new node();
u=u->child[c1][c2];
u->cnt++;
}
}
int solve(string s,string v) {
node* u=root;
int n=s.size(),m=v.size();
int len=min(n,m),head=0,tail=INT_MAX;
reverse(v.begin(),v.end());
for(int i=0;i<len;i++) {
if(u->child[getNum(s[i])][getNum(v[i])]==NULL) return 0;
u=u->child[getNum(s[i])][getNum(v[i])];
}
head=u->cnt;
queue<node*> q;q.push(u);
if(n<m) {
for(int i=n;i<m;i++) {
int c=getNum(v[i]),sz=q.size();
for(int j=0;j<sz;j++) {
node* top=q.front();q.pop();
for(int k=0;k<4;k++) if(top->child[k][c]!=NULL) q.push(top->child[k][c]);
}
}
}else if(n>m) {
for(int i=m;i<n;i++) {
int c=getNum(s[i]),sz=q.size();
for(int j=0;j<sz;j++) {
node* top=q.front();q.pop();
for(int k=0;k<4;k++) if(top->child[c][k]!=NULL) q.push(top->child[c][k]);
}
}
} else return head;
if(q.empty()) return 0;
tail=0;
while(!q.empty()) {
node* top=q.front();q.pop();
tail+=top->cnt;
}
return min(head,tail);
}
};
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
Trie trie;
int n,m;cin>>n>>m;
while(n--) {
string x;cin>>x;
trie.add(x);
}
while(m--) {
string u,v;cin>>u>>v;
cout << trie.solve(u,v)<<'\n';
}
return 0;
}
