#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int,int>;
using aa = array<int,3>;
const int N = 1e5+5;
string s[N];
int change(char c) {
if(c=='A') return 0;
if(c=='U') return 1;
if(c=='G') return 2;
return 3;
}
struct TRIYEUMINHEM {
int trie[N*20][4];
vector<int> a[N*20];
int timer=0;
void add(string s,int id) {
int u=0;
for(char c:s) {
int v=change(c);
if(!trie[u][v]) {
trie[u][v]=++timer;
}
u=trie[u][v];
a[u].push_back(id);
}
}
int get(string s,int l,int r) {
int u=0;
for(char c:s) {
int v=change(c);
if(!trie[u][v]) return 0;
u=trie[u][v];
}
int x=lower_bound(a[u].begin(),a[u].end(),l)-a[u].begin();
int y=upper_bound(a[u].begin(),a[u].end(),r)-a[u].begin();
return y-x;
}
ii getlr(string s) {
int u=0;
for(char c:s) {
int v=change(c);
if(!trie[u][v]) return {-1,-1};
u=trie[u][v];
}
return {*a[u].begin(),*a[u].rbegin()};
}
} rev,trie;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin >> n >> q;
for(int i=1;i<=n;i++) {
cin >> s[i];
}
sort(s+1,s+1+n);
for(int i=1;i<=n;i++) {
reverse(s[i].begin(),s[i].end());
rev.add(s[i],i);
reverse(s[i].begin(),s[i].end());
trie.add(s[i],i);
}
while(q--) {
string pre,suf;
cin >> pre >> suf;
reverse(suf.begin(),suf.end());
ii res=trie.getlr(pre);
if(res.fi==-1) cout << 0 << '\n';
else {
cout << rev.get(suf,res.fi,res.se) << '\n';
}
}
return 0;
}
