#include<bits/stdc++.h>
using namespace std;
const int N=2e6+6;
int n,q;
string s[N];
struct trie {
struct Node {
vector<int> v;
int child[4];
void init() {
memset(child,-1,sizeof(child));
}
} 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 p=0;
for (char c:s) {
int &nxt=node[p].child[c-'0'];
if (nxt==-1) {
nxt=new_node();
}
p=nxt;
node[p].v.push_back(id);
}
}
vector<int> get(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]);
}
for (int i=1; i<=n; ++i) {
t1.add(s[i],i);
reverse(s[i].begin(),s[i].end());
t2.add(s[i],i);
}
while (q--) {
string l,r;
cin>>l>>r;
compress(l); compress(r);
vector<int> a=t1.get(l);
vector<int> b=t2.get(r);
int i=0, j=0;
int res=0;
for (int i=0; i<a.size(); ++i) {
while (j<b.size() && b[j]<a[i]) ++j;
if (b[j]==a[i]) ++res;
}
cout<<res<<'\n';
}
return 0;
}
