#include <bits/stdc++.h>
using namespace std;
string a[100001], p[100001], q[100001], ra[100001];
int res[100001];
vector<int> tv[1000002], luu[1000002];
int sum[1000002];
int idx[26];
struct trie{
struct node{
int nxt[4];
int cnt;
node(){
nxt[0] = nxt[1]=nxt[2] = nxt[3] = 0;
cnt = 0;
}
};
vector<node> tr;
int lst = 1;
void init(){
tr.resize(1);
}
void add(string &s, int tro){
int moc = 0;
for (char i:s){
int id = idx[i-'A'];
if(tr[moc].nxt[id]==0){
node tmp;
tr.push_back(tmp);
tr[moc].nxt[id] = lst;
moc = lst;
lst++;
}else{
moc = tr[moc].nxt[id];
}
tr[moc].cnt++;
}
if(tro!=-1){
tv[moc].push_back(tro);
}
}
void cook(string &s, int tro){
int moc = 0;
for (char i:s){
int id = idx[i-'A'];
if(tr[moc].nxt[id]==0)break;
moc = tr[moc].nxt[id];
}
if(moc==0)return;
luu[moc].push_back(tro);
sum[moc] += a[tro].size();
}
int count(string &s){
int moc = 0;
for (char i:s){
int id = idx[i-'A'];
moc = tr[moc].nxt[id];
if(moc==0)return 0;
}
return tr[moc].cnt;
}
};
trie con[1000002];
trie cay;
void dfs(int u){
for (int i = 0;i<4;++i){
if(cay.tr[u].nxt[i]!=0){
dfs(cay.tr[u].nxt[i]);
int v = cay.tr[u].nxt[i];
if(sum[u] < sum[v]){
swap(con[u], con[v]);
swap(sum[u], sum[v]);
swap(luu[u], luu[v]);
}
for (int j:luu[v]){
con[u].add(ra[j], -1);
luu[u].push_back(j);
}
sum[u] += sum[v];
}
}
for (int i:tv[u]){
res[i] = con[u].count(q[i]);
// cout << u << ' ' << i << ' ' << q[i] << " NGU\n";
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n>> m;
for (int i = 1;i<=n;++i){
cin >> a[i];
ra[i] = a[i];
reverse(ra[i].begin(), ra[i].end());
}
idx['A'-'A'] = 0;
idx['C'-'A'] = 1;
idx['G'-'A'] = 2;
idx['U'-'A'] = 3;
cay.init();
for (int i = 1;i<=m;++i){
cin >> p[i] >> q[i];
reverse(q[i].begin(), q[i].end());
cay.add(p[i], i);
}
for (int i = 1;i<=n;++i){
cay.cook(a[i], i);
}
int lst = cay.lst;
// cout << lst << '\n';
for (int i = 0;i<lst;++i){
con[i].init();
for (int j:luu[i]){
con[i].add(ra[j], -1);
}
}
// cout << q[3];return 0;
// cout << con[3].lst;return 0;
// cout << luu[3].size();return 0;
// cout << con[3].count(q[3]);return 0;
dfs(0);
for (int i = 1;i<=m;++i){
cout << res[i] << '\n';
}
}
