#include <bits/stdc++.h>
using namespace std;
#define TASK "DELSEQ"
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define fi first
#define se second
#define hash vector<int>
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for (int i = (n); i >= 1; i--)
#define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++)
#define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--)
#define MASK(k) (1LL << (k))
#define BIT(i, n) (((n) >> ((i) - 1)) & 1)
#define OFF(i, n) ((n) & ~MASK((i) - 1))
#define ON(i, n) ((n) | MASK((i) - 1))
#define NUM_BIT(n) (__builtin_popcountll(n))
const int MAXN = 1e5 + 26;
int n, m, k;
string p, q, t, s[MAXN];
struct Node {
Node *child[4];
vector<int> pre;
int cnt = 0;
Node() { FOR(i, 0, 3) child[i] = nullptr; }
};
struct Trie {
Node *root;
Trie() {
root = new Node();
}
void add(string s, int r) {
int t = s.length();
Node* p = root;
root->pre.push_back(r);
REP(j, t) {
int i = s[j - 1] - 'A';
if (p->child[i] == nullptr) p->child[i] = new Node();
p = p->child[i];
p->pre.push_back(r);
}
p->cnt++;
}
} t1, t2, t3;
string res;
void dfs(Node *p, bool first) {
if (p->cnt > 0 && first) {
REP(i, p->cnt) s[++k] = res;
}
if (!first) sort(p->pre.begin(), p->pre.end());
FOR(i, 0, 3) if (p->child[i] != nullptr) {
char c = (char) ('A' + i);
res += c;
dfs(p->child[i], first);
res.pop_back();
}
}
string trans(string s) {
string res = "";
REP(i, s.length()) {
if (s[i - 1] == 'A') res += 'A';
if (s[i - 1] == 'G') res += 'B';
if (s[i - 1] == 'C') res += 'C';
if (s[i - 1] == 'U') res += 'D';
}
return res;
}
int find_index(string pre, bool upper) {
Node *p = t2.root;
REP(j, pre.length()) {
int i = pre[j - 1] - 'A';
if (p->child[i] == nullptr) return -1;
p = p->child[i];
}
if (upper) return p->pre.back();
return p->pre.front();
}
Node *find_node(string str) {
Node *p = t3.root;
REP(j, str.length()) {
int i = str[j - 1] - 'A';
if (p->child[i] == nullptr) return nullptr;
p = p->child[i];
}
return p;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
if (fopen(TASK ".INP", "r")) {
freopen(TASK ".INP", "r", stdin);
freopen(TASK ".OUT", "w", stdout);
}
cin >> n >> m;
REP(i, n) {
cin >> t;
t1.add(trans(t), -1);
}
dfs(t1.root, true);
REP(i, k) {
t2.add(s[i], i);
reverse(s[i].begin(), s[i].end());
t3.add(s[i], i);
}
dfs(t2.root, false);
dfs(t3.root, false);
while (m--) {
cin >> p >> q;
p = trans(p);
q = trans(q);
int l = find_index(p, false);
int r = find_index(p, true);
if (l == -1 || r == - 1) {
cout << 0 << endl;
continue;
}
reverse(q.begin(), q.end());
Node *node = find_node(q);
if (node == nullptr) {
cout << 0 << endl;
continue;
}
vector<int> &v = node->pre;
int lp = lower_bound(v.begin(), v.end(), l) - v.begin();
int rp = upper_bound(v.begin(), v.end(), r) - v.begin();
int res = rp - lp;
cout << res << endl;
}
return 0;
}
