#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e6+6;
int n,q;
string s[N];
struct trie {
struct Node {
vector<int> v;
int child[4];
int l,r;
void init() {
memset(child,-1,sizeof(child));
l=2e9, r=0;
}
} node[N];
int cur;
trie() {
cur=0;
node[cur].init();
}
int new_node() {
++cur;
node[cur].init();
return cur;
}
void add(string s, int id, int type) {
int p=0;
for (char c:s) {
int &nxt=node[p].child[c-'0'];
if (nxt==-1) {
nxt=new_node();
}
p=nxt;
if (type==2) node[p].v.push_back(id);
else { node[p].l=min(node[p].l,id); node[p].r=max(node[p].r,id); }
}
}
pii get1(string s) {
int p=0;
for (char c:s) {
p=node[p].child[c-'0'];
}
return make_pair(node[p].l,node[p].r);
}
vector<int> get2(string s) {
int p=0;
for (char c:s) {
p=node[p].child[c-'0'];
}
return node[p].v;
}
} t1,t2;
void compress(string &s) {
for (int i=0; i<s.length(); ++i) {
if (s[i]=='A') s[i]='0';
if (s[i]=='G') s[i]='1';
if (s[i]=='U') s[i]='2';
if (s[i]=='C') s[i]='3';
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin>>n>>q;
for (int i=1; i<=n; ++i) {
cin>>s[i];
compress(s[i]);
}
sort(s+1,s+1+n);
for (int i=1; i<=n; ++i) {
t1.add(s[i],i,1);
reverse(s[i].begin(),s[i].end());
t2.add(s[i],i,2);
}
while (q--) {
string s1,s2;
cin>>s1>>s2;
compress(s1); compress(s2);
pii range=t1.get1(s1);
vector<int> a=t2.get2(s2);
int l=lower_bound(a.begin(),a.end(),range.fi)-a.begin(); if (l==a.size()) { cout<<0<<'\n'; continue; }
int r=upper_bound(a.begin(),a.end(),range.se)-a.begin(); if (r==0) { cout<<0<<'\n'; continue; }
cout<<r-l+1<<'\n';
}
return 0;
}
