#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
const int N = 3e5 + 5;
map <char, int> code;
int n, q;
string prefix[N], suffix[N];
int ID[N];
struct PrefixTrie {
struct Node{
Node *child[5];
int min_id, max_id;
Node() {
min_id = 2e9;
max_id = - 2e9;
FOR(i, 1, 4) child[i] = NULL;
}
};
Node *root = new Node();
void addString (const string &s, int id) {
Node *p = root;
for (const char &c : s) {
int j = code[c];
if (p -> child[j] == NULL) p -> child[j] = new Node();
p = p -> child[j];
p -> min_id = min(p -> min_id, id);
p -> max_id = max(p -> max_id, id);
}
}
pair <int, int> get (const string &s) {
Node *p = root;
for (const char &c : s) {
int j = code[c];
if (p -> child[j] == NULL) return make_pair(- 1, - 1);
p = p -> child[j];
}
return make_pair(p -> min_id, p -> max_id);
}
} Trie1;
struct SuffixTrie {
struct Node{
Node *child[5];
vector <int> id;
Node() {
id.clear();
FOR(i, 1, 4) child[i] = NULL;
}
};
Node *root = new Node();
void addString (const string &s, int id) {
Node *p = root;
for (const char &c : s) {
int j = code[c];
if (p -> child[j] == NULL) p -> child[j] = new Node();
p = p -> child[j];
p -> id.push_back(id);
}
}
int get (const string &s, int L, int R) {
if (L == - 1 || R == - 1) return 0;
Node *p = root;
for (const char &c : s) {
int j = code[c];
if (p -> child[j] == NULL) return 0;
p = p -> child[j];
}
return upper_bound(p -> id.begin(), p -> id.end(), R) - lower_bound(p -> id.begin(), p -> id.end(), L);
}
} Trie2;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define ko "kieuoanh"
if (fopen(ko".inp", "r")) {
freopen(ko".inp", "r", stdin);
freopen(ko".out", "w", stdout);
}
cin >> n >> q;
code['A'] = 1;
code['U'] = 2;
code['G'] = 3;
code['C'] = 4;
FOR(i, 1, n) {
cin >> prefix[i];
suffix[i] = prefix[i];
reverse(suffix[i].begin(), suffix[i].end());
ID[i] = i;
}
sort(ID + 1, ID + 1 + n, [&] (int x, int y) {
return prefix[x] < prefix[y];
});
FOR(i, 1, n) {
Trie1.addString(prefix[ID[i]], i);
Trie2.addString(suffix[ID[i]], i);
}
while (q--) {
string P, Q; cin >> P >> Q;
pair <int, int> tam = Trie1.get(P);
reverse(Q.begin(), Q.end());
cout << Trie2.get(Q, tam.first, tam.second) << "\n";
}
cerr << "\n[Time Elapsed] " << 0.001 * clock() << "s\n";
return 0;
}
