#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long
const intt mod = 1e9 + 7;
const intt base = 41;
const intt inf = 1e18;
const intt mxN = 5005;
const intt L = 21;
intt f(char c) {
if(c == 'A') return 0;
if(c == 'C') return 1;
if(c == 'G') return 2;
return 3;
}
struct trie {
trie *kids[4];
intt mn, mx;
trie () {
for(intt i = 0; i < 4; i++) {
kids[i] = nullptr;
}
mn = inf, mx = -inf;
}
};
void add(trie *&root, string s, intt idx) {
trie *node = root;
intt N = (intt)s.size();
for(intt i = 0; i < N; i++) {
intt num = f(s[i]);
if(node->kids[num] == nullptr) {
node->kids[num] = new trie();
}
node = node->kids[num];
node->mn = min(node->mn, idx);
node->mx = max(node->mx, idx);
}
}
//-------------------------------------------------------------------------------------------------------------------------------------------------------
struct rtrie{
rtrie *kids[4];
vector<intt> data;
rtrie () {
for(intt i = 0; i < 4; i++) {
kids[i] = nullptr;
}
data.clear();
}
};
void radd(rtrie *& root, string s, intt idx) {
rtrie *node = root;
intt N = (intt)s.size();
for(intt i = 0; i < N; i++) {
intt num = f(s[i]);
if(node->kids[num] == nullptr) {
node->kids[num] = new rtrie();
}
node = node->kids[num];
node->data.pb(idx);
}
}
void solve() {
intt N, M;
cin >> N >> M;
trie *root = new trie();
rtrie *rroot = new rtrie();
vector<string> words;
for(intt i = 0; i < N; i++) {
string s;
cin >> s;
words.pb(s);
}
sort(ALL(words));
for(intt i = 0; i < N; i++) {
string s = words[i];
add(root, s, i);
reverse(ALL(s));
radd(rroot, s, i);
}
for(intt i = 0; i < M; i++) {
string pre, suf;
cin >> pre >> suf;
reverse(ALL(suf));
trie *node = root;
for(intt j = 0; j < pre.size(); j++) {
intt num = f(pre[j]);
if(node->kids[num] != nullptr) {
node = node->kids[num];
} else {
node = nullptr;
break;
}
}
if(node == nullptr) {
cout << 0 << endl;
continue;
}
rtrie *rnode = rroot;
for(intt j = 0; j < suf.size(); j++) {
intt num = f(suf[j]);
if(rnode->kids[num] != nullptr) {
rnode = rnode->kids[num];
} else {
rnode = nullptr;
break;
}
}
if(rnode == nullptr) {
cout << 0 << endl;
continue;
}
vector<intt> v = rnode->data;
cout << upper_bound(ALL(v), node->mx) - lower_bound(ALL(v), node->mn) << endl;
// cout << node->mn << " " << node->mx << " :::: ";
// for(intt j : v) cout << j << " ";
// cout << endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
intt tst = 1;
// cin >> tst;
while (tst--) {
solve();
}
}
