#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const int N = 1e5 + 5;
const int M = 2e6 + 5;
int getId(char c) {
if (c == 'A') return 0;
if (c == 'U') return 1;
if (c == 'G') return 2;
if (c == 'C') return 3;
}
struct Trie {
struct Node{
int child[4];
int l, r;
vector<int> vec;
Node() {
memset(child, -1, sizeof(child));
r = -1;
l = 1e9;
}
};
Trie() {}
Node nodes[M];
int cur = 0;
void add(const string &s, int id) {
int pos = 0;
for (auto it : s) {
int c = getId(it);
if (nodes[pos].child[c] == -1) {
cur++;
nodes[pos].child[c] = cur;
nodes[cur] = Node();
}
pos = nodes[pos].child[c];
nodes[pos].l = min(nodes[pos].l, id);
nodes[pos].r = max(nodes[pos].r, id);
}
}
pii get(string &p) {
int pos = 0;
for (auto it : p) {
int c = getId(it);
if (nodes[pos].child[c] == -1) {
return {1e9, -1};
}
pos = nodes[pos].child[c];
}
return {nodes[pos].l, nodes[pos].r};
}
void addSuffix(const string &s, int id) {
int pos = 0;
for (auto it : s) {
int c = getId(it);
if (nodes[pos].child[c] == -1) {
cur++;
nodes[pos].child[c] = cur;
nodes[cur] = Node();
}
pos = nodes[pos].child[c];
// cout << pos << ' ' << it << '\n';
nodes[pos].vec.pb(id);
}
}
int query(const string &q, int l, int r) {
int pos = 0;
for (auto it : q) {
int c = getId(it);
if (nodes[pos].child[c] == -1) {
return 0;
}
pos = nodes[pos].child[c];
}
// for (auto it : nodes[pos].vec) {
// cout << it << " ";
// }cout << endl;
int x = upper_bound(nodes[pos].vec.begin(), nodes[pos].vec.end(), r) - lower_bound(nodes[pos].vec.begin(), nodes[pos].vec.end(), l);
return x;
}
};
Trie chim;
Trie tri;
int n, m;
string s[N];
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
sort(s + 1, s + 1 + n);
for (int i = 1; i <= n; i++) {
chim.add(s[i], i);
reverse(s[i].begin(), s[i].end());
tri.addSuffix(s[i], i);
}
for (int i = 1; i <= m; i++) {
string p, q;
cin >> p >> q;
pii x = chim.get(p);
if (x.F == 1000000000) {
cout << 0 << '\n';
continue;
}
reverse(q.begin(), q.end());
cout << tri.query(q, x.F, x.S) << '\n';
}
}
