#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int N = 1e5 + 5,
INF = 1e9;
int n, m;
string s[N];
int id(char x){
if(x == 'A') return 0;
if(x == 'C') return 1;
if(x == 'G') return 2;
if(x == 'U') return 3;
}
struct Trie1{
struct node{
node* child[4];
int l, r;
node(): l(INF), r(-INF) {
child[0] = child[1] = child[2] = child[3] = NULL;
}
};
node* root;
Trie1(): root(new node()){}
void add(string &s, int idx){
auto p = root;
for(auto ch : s){
int c = id(ch);
if(!p->child[c]) p->child[c] = new node();
p = p->child[c];
p->l = min(p->l, idx);
p->r = max(p->r, idx);
}
}
ii query(string &s){
auto p = root;
for(auto ch : s){
int c = id(ch);
if(!p->child[c]) return {-1, -1};
p = p->child[c];
}
return {p->l, p->r};
}
} d1;
struct Trie2{
struct node{
node* child[4];
vector<int> pos;
node(){
child[0] = child[1] = child[2] = child[3] = NULL;
}
};
node* root;
Trie2(): root(new node()) {}
void add(string &s, int idx){
auto p = root;
for(auto ch : s){
int c = id(ch);
if(!p->child[c]) p->child[c] = new node();
p = p->child[c];
p->pos.push_back(idx);
}
}
int query(string &s, int l, int r){
auto p = root;
for(auto ch : s){
int c = id(ch);
if(!p->child[c]) return 0;
p = p->child[c];
}
int tl = lower_bound(p->pos.begin(), p->pos.end(), l) - p->pos.begin(),
tr = upper_bound(p->pos.begin(), p->pos.end(), r) - p->pos.begin() - 1;
return tr - tl + 1;
}
} d2;
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> s[i];
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i++){
d1.add(s[i], i);
reverse(s[i].begin(), s[i].end());
d2.add(s[i], i);
}
while(m--){
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
auto range = d1.query(p);
if(range == make_pair(-1, -1)) cout << 0 << "\n";
else{
cout << d2.query(q, range.first, range.second) << "\n";
}
}
return 0;
}
