#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
struct Node {
int child[4];
vector<int> ids;
Node() { memset(child, -1, sizeof(child)); }
};
struct Trie {
vector<Node> t;
Trie() { t.emplace_back(); }
void add(string &s, int id) {
int p=0;
for (char c:s) {
int x=c-'0';
if (t[p].child[x]==-1) {
t[p].child[x]=t.size();
t.emplace_back();
}
p=t[p].child[x];
t[p].ids.push_back(id);
}
}
pair<int,int> get(string &s) {
int p=0;
for (char c:s) {
int x=c-'0';
if (t[p].child[x]==-1) return {2e9,0};
p=t[p].child[x];
}
return {t[p].ids.front(), t[p].ids.back()};
}
};
void compress(string &s) {
for (char &c:s) {
if (c=='A') c='0';
else if (c=='G') c='1';
else if (c=='U') c='2';
else if (c=='C') c='3';
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n,q; cin>>n>>q;
vector<string> s(n+1);
for (int i=1;i<=n;i++) cin>>s[i];
vector<string> rev=s;
for (int i=1;i<=n;i++) reverse(rev[i].begin(), rev[i].end());
Trie pre,suf;
vector<int> id(n); iota(id.begin(), id.end(), 1);
sort(id.begin(), id.end(), [&](int a,int b){return s[a]<s[b];});
for (int i=0;i<n;i++) {
string x=s[id[i]];
compress(x);
pre.add(x,i);
}
sort(id.begin(), id.end(), [&](int a,int b){return rev[a]<rev[b];});
for (int i=0;i<n;i++) {
string x=rev[id[i]];
compress(x);
suf.add(x,i);
}
while(q--) {
string p,q; cin>>p>>q;
compress(p); compress(q);
reverse(q.begin(),q.end());
auto range1=pre.get(p);
auto range2=suf.get(q);
if (range1.fi>range1.se || range2.fi>range2.se) {
cout<<0<<'\n';
continue;
}
vector<int> a;
for (int i=range2.fi;i<=range2.se;i++) a.push_back(i);
int l=lower_bound(a.begin(),a.end(),range1.fi)-a.begin();
int r=upper_bound(a.begin(),a.end(),range1.se)-a.begin();
cout<<r-l<<'\n';
}
}
