#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int to(char c) {
if (c == 'A') return 0;
else if (c == 'C') return 1;
else if (c == 'G') return 2;
else return 3;
}
int n, q;
string s[N];
int tot;
int l[275 * N];
int r[275 * N];
int sz[275 * N];
int nxt[275 * N][4];
int root;
int T[N << 2];
int nxtNode() {
return ++tot;
}
void add(int root, string s, int id = 0) {
int cur = root;
for (char c : s) {
c = (int) to(c);
if (!nxt[cur][c]) {
nxt[cur][c] = nxtNode();
}
cur = nxt[cur][c];
if (l[cur] == 0) {
l[cur] = id;
}
r[cur] = id;
++sz[cur];
}
}
int getNode(int root, string s) {
int cur = root;
for (char c : s) {
c = (int) to(c);
if (!nxt[cur][c]) {
return 0;
}
cur = nxt[cur][c];
}
return cur;
}
#define mid ((l + r) >> 1)
void build(int v, int l, int r) {
T[v] = nxtNode();
for (int i = l; i <= r; ++i) {
add(T[v], s[i]);
}
if (l < r) {
build(v << 1, l, mid);
build(v << 1 | 1, mid + 1, r);
}
}
int getCount(int v, int l, int r, int L, int R, string &s) {
if (L <= l && r <= R) {
return sz[getNode(T[v], s)];
}
int ans = 0;
if (L <= mid) ans += getCount(v << 1, l, mid, L, R, s);
if (mid < R) ans += getCount(v << 1 | 1, mid + 1, r, L, R, s);
return ans;
}
int solve(string p, string q) {
int cur = getNode(root, p);
if (!cur) return 0;
reverse(q.begin(), q.end());
return getCount(1, 1, n, l[cur], r[cur], q);
}
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
sort(s + 1, s + 1 + n);
root = nxtNode();
for (int i = 1; i <= n; ++i) {
add(root, s[i], i);
reverse(s[i].begin(), s[i].end());
}
build(1, 1, n);
while (q--) {
string u, v;
cin >> u >> v;
cout << solve(u, v) << '\n';
}
}
