#include<bits/stdc++.h>
using namespace std;
vector<int> st[2000005];
int trie[2][2000005][4], num[2000005], sz[2];
void add(int b, string s, int idx)
{
if(b == 1){
reverse(s.begin(), s.end());
}
int u = 0;
for(int i = 0; i < s.size(); i++){
if(trie[b][u][s[i] - 'A'] == 0) trie[b][u][s[i] - 'A'] = ++sz[b];
u = trie[b][u][s[i] - 'A'];
if(b == 0) num[u]++;
else st[u].push_back(idx);
}
}
string curstr = "";
int cc = 0;
void dfs(int u)
{
//On trie 0 only
int curnum = num[u];
for(int i = 0; i < 4; i++) curnum -= num[trie[0][u][i]];
if(curstr.size() > 0) while(curnum--) add(1, curstr, ++cc);
for(int i = 0; i < 4; i++){
curstr.push_back(i + 'A');
if(trie[0][u][i] > 0) dfs(trie[0][u][i]);
curstr.pop_back();
}
}
pair<int, int> get_range(string s)
{
int pref = 0, u = 0;
for(int i = 0; i < s.size(); i++){
for(int j = 0; j < s[i] - 'A'; j++) pref += num[trie[0][u][j]];
u = trie[0][u][s[i] - 'A'];
if(u == 0) return {-1, -1};
}
return make_pair(pref+1, pref + num[u]);
}
string format(string s)
{
//Format to ABCD
for(auto &i : s){
if(i == 'A') i = 'A';
else if(i == 'C') i = 'B';
else if(i == 'G') i = 'C';
else i = 'D';
}
return s;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q; cin>>n>>q;
for(int i = 1; i <= n; i++){
string s; cin>>s;
add(0, format(s), -1);
}
dfs(0);
//Now solve
for(int test = 0; test < q; test++){
string pref, suf; cin>>pref>>suf;
pref = format(pref); suf = format(suf);
pair<int, int> range = get_range(pref);
int u = 0;
for(int i = 0; i < suf.size(); i++){
u = trie[1][u][suf[i] - 'A'];
if(u == 0) break;
}
int ans = upper_bound(st[u].begin(), st[u].end(), range.second) - lower_bound(st[u].begin(), st[u].end(), range.first);
cout<<ans<<'\n';
}
}
