#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define emb emplace_back
#define pii pair <int, int>
#define fi first
#define se second
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define Task "rna"
template <class T> bool minimize(T &a, T b) {
if (a > b) return a = b, true;
return false;
}
template <class T> bool maximize(T &a, T b) {
if (a < b) return a = b, true;
return false;
}
const int N = 1e5 + 5, mod = 1e9 + 321, base = 311;
const ll INF = 1e18;
const int root = 0;
int cntNode = 0;
struct Node {
int child[4], cnt;
Node () {
memset(child, -1, sizeof child);
cnt = 0;
}
} node[N * 20 * 4];
void add(string &str) {
int p = root;
for (char c: str) {
int k = c - 'A';
if (node[p].child[c] == -1)
node[p].child[c] = ++cntNode;
p = node[p].child[c]; ++node[p].cnt;
}
}
int get(string &str) {
int p = root;
for (char c: str) {
int k = c - 'A';
if (node[p].child[c] == -1) return 0;
p = node[p].child[c];
}
return node[p].cnt;
}
int n, m;
string s[N], r[N];
string p[N], q[N];
vector <tuple <string, int, int>> query[N];
string decode(string str) {
for (char &c: str) {
if (c == 'C') c = 'B';
else if (c == 'G') c = 'C';
else if (c == 'U') c = 'D';
}
return str;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i]; s[i] = decode(s[i]);
}
sort (s + 1, s + n + 1);
for (int i = 1; i <= n; i++) {
r[i] = s[i]; reverse(r[i].begin(), r[i].end());
}
int outID = n + 1;
for (int i = 0; i < m; i++) {
cin >> p[i] >> q[i];
p[i] = decode(p[i]); q[i] = decode(q[i]);
reverse(q[i].begin(), q[i].end());
int L = lower_bound(s + 1, s + n + 1, p[i]) - s;
int R = upper_bound(s + L, s + n + 1, p[i] + 'z') - s - 1;
if (L <= R) {
query[L - 1].emb(q[i], i, -1);
query[R].emb(q[i], i, 1);
}
// cerr << L << ' ' << R << '\n';
}
vector <int> ans(m);
for (int i = 1; i <= n; i++) {
add(r[i]);
for (int _ = 0; _ < query[i].size(); _++) {
string &q = get<0>(query[i][_]);
int id = get<1>(query[i][_]), b = get<2>(query[i][_]);
ans[id] += b * get(q);
}
}
for (int x: ans) cout << x << '\n';
}
