#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<string,int> psi;
const int N = 1e5;
const int MAXN = 2e6;
struct trie{
int nxt[4];
vector<int> isi;
};
trie dep[MAXN+5], bel[MAXN+5];
int cntDep = 0;
int cntBel = 0;
int getNum(char x){
if(x == 'A') return 0;
if(x == 'G') return 1;
if(x == 'C') return 2;
return 3;
}
void insert(int node, string &s, int idx, int id, trie *t, int &cnt){
t[node].isi.push_back(idx);
if(id == s.size()) return;
int cur = getNum(s[id]);
if(t[node].nxt[cur] == -1) {
cnt++;
memset(t[cnt].nxt,-1,sizeof(t[cnt].nxt));
t[node].nxt[cur] = cnt;
}
insert(t[node].nxt[cur], s, idx, id+1, t, cnt);
}
vector<int> query(int node, string &s, int id, trie *t){
if(node == -1) return vector<int>();
if(id == s.size()) {
return t[node].isi;
}
int cur = getNum(s[id]);
return query(t[node].nxt[cur], s, id+1, t);
}
string li[N+5];
int n,m;
string pre[N+5], suf[N+5];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> li[i];
}
sort(li+1,li+n+1);
memset(dep[0].nxt,-1,sizeof(dep[0].nxt));
memset(bel[0].nxt,-1,sizeof(bel[0].nxt));
for(int i=1;i<=n;i++){
insert(0, li[i], i, 0, dep, cntDep);
string rev = li[i];
reverse(rev.begin(), rev.end());
insert(0, rev, i, 0, bel, cntBel);
}
for(int i=1;i<=m;i++){
cin >> pre[i] >> suf[i];
reverse(suf[i].begin(), suf[i].end());
vector<int> retPre = query(0, pre[i], 0, dep);
if(retPre.size() == 0) {
cout << "0\n";
continue;
}
vector<int> retSuf = query(0, suf[i], 0, bel);
int l = retPre[0];
int r = retPre.back();
int idl = lower_bound(retSuf.begin(), retSuf.end(), l) - retSuf.begin();
int idr = upper_bound(retSuf.begin(), retSuf.end(), r) - retSuf.begin();
cout << idr-idl << "\n";
}
return 0;
}
