#include <bits/stdc++.h>
using namespace std;
int index(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
return 3;
}
struct trie{
vector<vector<int>> t;
vector<vector<int>> inds;
int uj_pont(){
t.push_back(vector<int>(4, -1));
inds.push_back(vector<int>());
return (int)t.size()-1;
}
void init(){
uj_pont();
}
int add(string s, int ind){
int x = 0;
for(char &c : s){
int y = index(c);
if(t[x][y] == -1)
t[x][y] = uj_pont();
x = t[x][y];
}
inds[x].push_back(ind);
return x;
}
};
vector<vector<int>> query;
vector<int> ert, veg, ki;
vector<string> vs;
trie t1, t2;
void add(trie &t, string s){
int x = 0;
for(char &c : s){
ert[x]++;
int y = index(c);
if(t.t[x][y] == -1)
return;
x = t.t[x][y];
}
ert[x]++;
return;
}
void add_querry(trie &t, string s, int ind){
int x = 0;
for(char &c : s){
int y = index(c);
if(t.t[x][y] == -1)
return;
x = t.t[x][y];
}
query[x].push_back(ind);
return;
}
void bejar(trie &t, int x){
for(int &y : query[x])
ki[y] = -ert[veg[y]];
for(int y : t.inds[x])
add(t2, vs[y]);
for(int i = 0; i < 4; i++)
if(t.t[x][i] != -1)
bejar(t, t.t[x][i]);
for(int &y : query[x])
ki[y] += ert[veg[y]];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin>>n>>m;
t1.init();
t2.init();
vs.resize(n);
for(int i = 0; i < n; i++){
cin>>vs[i];
t1.add(vs[i], i);
reverse(vs[i].begin(), vs[i].end());
}
query.resize(t1.t.size());
ki.resize(m);
veg.resize(m);
for(int i = 0; i < m; i++){
string a, b;
cin>>a>>b;
add_querry(t1, a, i);
reverse(b.begin(), b.end());
veg[i] = t2.add(b, i);
}
ert.resize(t2.t.size(), 0);
bejar(t1, 0);
for(int x : ki)
cout<<x<<"\n";
return 0;
}
