#include <bits/stdc++.h>
using namespace std;
#define kien long long
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pb push_back
#define pii pair <int, int>
const int MXN = 2e5 + 5;
const int base = 31;
kien ans, n, k, m;
string s[MXN];
kien dp[MXN], c[MXN];
map <int, int> pp;
struct KBB {
vector <int> vec;
KBB *nxt[5];
KBB() {
FOR (i, 0, 3) nxt[i] = NULL;
vec.clear();
}
};
void change (string &s) {
FOR (i, 0, s.size() - 1) {
if (s[i] == 'A') s[i] = 0;
else if (s[i] == 'U') s[i] = 1;
else if (s[i] == 'G') s[i] = 2;
else s[i] = 3;
}
}
void add (KBB *root, string s, int id) {
KBB *cur = root;
for (char c : s) {
if (cur->nxt[c] == NULL) cur->nxt[c] = new KBB();
cur = cur->nxt[c];
cur->vec.pb(id);
}
}
pii get (KBB *root, string &s) {
KBB *cur = root;
for (char c : s) {
if (cur->nxt[c] != NULL) cur = cur->nxt[c];
else return {-1, -1};
}
return {cur->vec[0], cur->vec.back()};
}
void xuly(KBB *root, KBB *rev, string x, string d) {
pii range = get(root, x);
if (range == make_pair(-1, -1)) {
cout << 0 << "\n"; return;
}
KBB *cur = rev;
for (char c : d) {
if (cur->nxt[c] != NULL) cur = cur->nxt[c];
else {
cout << 0 << "\n"; return;
}
}
cout << upper_bound(cur->vec.begin(), cur->vec.end(), range.second) - lower_bound(cur->vec.begin(), cur->vec.end(), range.first) << "\n";
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR (i, 1, n) cin >> s[i], change(s[i]);
sort (s + 1, s + 1 + n);
KBB *root = new KBB();
KBB *rev = new KBB();
FOR (i, 1, n) {
add(root, s[i], i);
reverse(s[i].begin(), s[i].end());
add(rev, s[i], i);
}
FOR (i, 1, m) {
string x, d;
cin >> x >> d; reverse(d.begin(), d.end());
change(x); change(d);
xuly(root, rev, x, d);
}
}
