#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define INF 0x3f3f3f3f
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define el cout << '\n'
#define maxn int(1e6 + 5)
using namespace std;
typedef pair<int, int> pii;
int n, q, pos[maxn];
string pre[maxn], suf[maxn];
int change(char c) {
if(c == 'A') return 1;
if(c == 'U') return 2;
if(c == 'G') return 3;
if(c == 'C') return 4;
return 0;
}
struct PrefixTree {
struct Node {
Node* child[5];
int mx, mn;
Node() {
memset(child, 0, sizeof child);
mx = -INF, mn = INF;
}
};
Node* root = new Node();
void build(string &s, int id) {
Node* u = root;
FOR(i, 0, s.size() - 1) {
int k = change(s[i]);
if(u -> child[k] == 0) u -> child[k] = new Node();
u = u -> child[k];
u -> mn = min(u -> mn, id);
u -> mx = max(u -> mx, id);
}
}
pii get(string &s) {
Node* u = root;
FOR(i, 0, s.size() - 1) {
int k = change(s[i]);
if(u -> child[k] == 0) return {-1, -1};
u = u -> child[k];
}
return {u -> mn, u -> mx};
}
} prefix;
struct SuffixTree {
struct Node {
Node* child[5];
vector<int> id;
Node() {
memset(child, 0, sizeof child);
id.clear();
}
};
Node* root = new Node();
void build(string &s, int id) {
Node* u = root;
FOR(i, 0, s.size() - 1) {
int k = change(s[i]);
if(u -> child[k] == 0) u -> child[k] = new Node();
u = u -> child[k];
u -> id.push_back(id);
}
}
int get(string &s, int l, int r) {
if(l == -1 || r == -1) return 0;
Node* u = root;
FOR(i, 0, s.size() - 1) {
int k = change(s[i]);
if(u -> child[k] == 0) return 0;
u = u -> child[k];
}
return upper_bound(u -> id.begin(), u -> id.end(), r) - lower_bound(u -> id.begin(), u -> id.end(), l);
}
} suffix;
bool cmp(int x, int y) {
return pre[x] < pre[y];
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
FOR(i, 1, n) {
cin >> pre[i];
suf[i] = pre[i];
reverse(suf[i].begin(), suf[i].end());
pos[i] = i;
}
sort(pos + 1, pos + n + 1, cmp);
FOR(i, 1, n) {
prefix.build(pre[pos[i]], i);
suffix.build(suf[pos[i]], i);
}
while(q--) {
string P, Q;
cin >> P >> Q;
reverse(Q.begin(), Q.end());
cout << suffix.get(Q, prefix.get(P).first, prefix.get(P).second), el;
}
return 0;
}
