#include <bits/stdc++.h>
#define hash _hash_
#define y1 _y1_
#define dec _dec_
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll MOD = 1e9 + 7;
const ll oo = 1e18;
/*----------- I alone decide my fate! ------------*/
/* I just do what I gotta, in the heat of the summer... */
// mapping: A -> 0, G -> 1, C -> 2, U -> 3
int get_val(char c) {
if (c == 'A') return 0;
if (c == 'G') return 1;
if (c == 'C') return 2;
return 3;
}
// so sánh theo thứ tự A < G < C < U
bool cmp_str(const string &a, const string &b) {
int n = (int)a.size(), m = (int)b.size();
int k = min(n, m);
for (int i = 0; i < k; ++i) {
int xa = get_val(a[i]);
int xb = get_val(b[i]);
if (xa != xb) return xa < xb;
}
return n < m;
}
// trie tiền tố (để lấy khoảng [L, R] các xâu có tiền tố p)
#define MAXNODE 2000005
int ch1[MAXNODE][4];
int L1[MAXNODE], R1[MAXNODE];
int cur1;
void pref_init() {
cur1 = 0;
for (int j = 0; j < 4; ++j) ch1[0][j] = -1;
L1[0] = 1000000000; R1[0] = -1000000000;
}
int pref_new() {
++cur1;
for (int j = 0; j < 4; ++j) ch1[cur1][j] = -1;
L1[cur1] = 1000000000; R1[cur1] = -1000000000;
return cur1;
}
void pref_add(const string &s, int id) {
int u = 0;
for (char c : s) {
int t = get_val(c);
if (ch1[u][t] == -1) ch1[u][t] = pref_new();
u = ch1[u][t];
if (L1[u] > id) L1[u] = id;
if (R1[u] < id) R1[u] = id;
}
}
void pref_get_range(const string &s, int &L, int &R) {
int u = 0;
for (char c : s) {
int t = get_val(c);
if (ch1[u][t] == -1) { L = -1; R = -1; return; }
u = ch1[u][t];
}
L = L1[u]; R = R1[u];
}
// trie hậu tố trên xâu đảo (để đếm số id thuộc [L, R] có hậu tố q)
int ch2[MAXNODE][4];
vector<int> ids2[MAXNODE];
int cur2;
void suf_init() {
cur2 = 0;
for (int j = 0; j < 4; ++j) ch2[0][j] = -1;
ids2[0].clear();
}
int suf_new() {
++cur2;
for (int j = 0; j < 4; ++j) ch2[cur2][j] = -1;
ids2[cur2].clear();
return cur2;
}
void suf_add(string s, int id) {
reverse(s.begin(), s.end());
int u = 0;
for (char c : s) {
int t = get_val(c);
if (ch2[u][t] == -1) ch2[u][t] = suf_new();
u = ch2[u][t];
ids2[u].push_back(id); // id tăng dần
}
}
int suf_query(string s, int L, int R) {
reverse(s.begin(), s.end());
int u = 0;
for (char c : s) {
int t = get_val(c);
if (ch2[u][t] == -1) return 0;
u = ch2[u][t];
}
const vector<int> &v = ids2[u];
int l = (int)(lower_bound(v.begin(), v.end(), L) - v.begin());
int r = (int)(upper_bound(v.begin(), v.end(), R) - v.begin()) - 1;
if (l > r) return 0;
return r - l + 1;
}
void solve() {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end(), cmp_str);
pref_init();
suf_init();
for (int i = 0; i < n; ++i) {
pref_add(a[i], i + 1);
suf_add(a[i], i + 1);
}
while (m--) {
string p, q;
cin >> p >> q;
int L, R;
pref_get_range(p, L, R);
if (L == -1) {
cout << 0 << '\n';
} else {
cout << suf_query(q, L, R) << '\n';
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
solve();
}
/*
How can you see into my eyes, like open doors?
Leading you down into my core, where I've become so numb
Without a soul, my spirit's sleeping somewhere cold
Until you find it here and bring it back home!
Wake me up! Wake me up inside
Cant wake up? Wake me up inside
*/
