#include <bits/stdc++.h>
using namespace std;
struct Trie {
struct node{
node* child[26][26];
int cnt;
node() {
for(int i=0;i<26;i++) for(int j=0;j<26;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=s[i]-'A',c2=s[n-i-1]-'A';
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[s[i]-'A'][v[i]-'A']==NULL) return 0;
u=u->child[s[i]-'A'][v[i]-'A'];
}
head=u->cnt;
queue<node*> q;q.push(u);
if(n<m) {
for(int i=n;i<m;i++) {
int c=v[i]-'A',sz=q.size();
for(int j=0;j<sz;j++) {
node* top=q.front();q.pop();
for(int k=0;k<26;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=s[i]-'A',sz=q.size();
for(int j=0;j<sz;j++) {
node* top=q.front();q.pop();
for(int k=0;k<26;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;
}
