#include<bits/stdc++.h>
#define int int64_t
constexpr int MOD = 1e9 + 7;
const int MAX_NODES = 2000006;
const int MAX_N = 100005;
constexpr int CHAR = 4;
using namespace std;
int N, M;
int pref_trie[MAX_NODES][4], suff_trie[MAX_NODES][4];
int pref_L[MAX_NODES], pref_R[MAX_NODES], suff_L[MAX_NODES], suff_R[MAX_NODES];
int pref_ptr = 1, suff_ptr = 1, timer_p = 0, timer_s = 0;
pair<int, int> points[MAX_N];
map<char, int> char_ind = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
int insert(int trie[][4], string &s, int &ptr) {
int node = 0;
for (char c : s) {
int v = char_ind[c];
if (trie[node][v] == 0) trie[node][v] = ptr++;
node = trie[node][v];
}
return node;
}
void dfs(int u, int trie[][4], int L[], int R[], int &timer) {
L[u] = ++timer;
for (int i = 0; i < 4; i++) {
if (trie[u][i] != 0) dfs(trie[u][i], trie, L, R, timer);
}
R[u] = timer;
}
int get_node(int trie[][4], string &s) {
int node = 0;
for (char c : s) {
int v = char_ind[c];
if (trie[node][v] == 0) return -1;
node = trie[node][v];
}
return node;
}
struct QueryEvent {
int x, y1, y2, id, weight;
};
int bit[MAX_NODES];
void update(int idx, int val) {
for (; idx < MAX_NODES; idx += idx & -idx) bit[idx] += val;
}
int query_bit(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
int ans[MAX_N];
void solve() {
cin >> N >> M;
vector<string> S(N);
for (int i = 0; i < N; i++) {
cin >> S[i];
int u = insert(pref_trie, S[i], pref_ptr);
reverse(S[i].begin(), S[i].end());
int v = insert(suff_trie, S[i], suff_ptr);
points[i] = {u, v};
}
dfs(0, pref_trie, pref_L, pref_R, timer_p);
dfs(0, suff_trie, suff_L, suff_R, timer_s);
vector<pair<int, int>> coords;
for (int i = 0; i < N; i++) {
coords.emplace_back(pref_L[points[i].first], suff_L[points[i].second]);
}
sort(coords.begin(), coords.end());
vector<QueryEvent> events;
for (int i = 0; i < M; i++) {
string P, Q;
cin >> P >> Q;
reverse(Q.begin(), Q.end());
int node_p = get_node(pref_trie, P);
int node_q = get_node(suff_trie, Q);
if (node_p != -1 && node_q != -1) {
int x1 = pref_L[node_p], x2 = pref_R[node_p];
int y1 = suff_L[node_q], y2 = suff_R[node_q];
events.push_back({x1 - 1, y1, y2, i, -1});
events.push_back({x2, y1, y2, i, 1});
}
}
sort(events.begin(), events.end(), [](QueryEvent a, QueryEvent b) {
return a.x < b.x;
});
int pt = 0;
for (auto &e : events) {
while (pt < N && coords[pt].first <= e.x) {
update(coords[pt].second, 1);
pt++;
}
ans[e.id] += e.weight * (query_bit(e.y2) - query_bit(e.y1 - 1));
}
for (int i = 0; i < M; i++) cout << ans[i] << "\n";
}
signed main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int test = 1;
//cin>>test;
while (test--) {
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << static_cast<double>(elapsed.count()) * 1e-9 << " seconds.\n";
return 0;
}
