#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
}
const int N = 1e5+5;
int id[256];
void prep() {
id['A'] = 0;
id['G'] = 1;
id['C'] = 2;
id['U'] = 3;
}
struct node {
int child[4];
int mn = N, mx = -N, cnt = 0;
node() { memset(child, -1, sizeof(child)); }
};
int n, m, ret[N];
string s[N], q[N];
vector<node> trie(1);
vector<int> evts[N];
void add(string s, int idx) {
int cur = 0, n = s.size();
for(char c : s) {
int ch = id[c];
if (trie[cur].child[ch] == -1) {
trie[cur].child[ch] = sz(trie);
trie.push_back(node());
}
cur = trie[cur].child[ch];
trie[cur].cnt += 1;
trie[cur].mn = min(trie[cur].mn, idx);
trie[cur].mx = max(trie[cur].mx, idx);
}
}
int get(string s) {
int cur = 0;
for(char c : s) {
int ch = id[c];
if (trie[cur].child[ch] == -1) return -1;
cur = trie[cur].child[ch];
}
return cur;
}
int main() {
setIO();
prep();
cin >> n >> m;
foru(i, 1, n) cin >> s[i];
sort(s+1, s+n+1);
foru(i, 1, n) add(s[i], i);
foru(i, 1, m) {
string p;
cin >> p >> q[i];
reverse(all(q[i]));
int tmp = get(p);
if (tmp != -1) {
int l = trie[tmp].mn, r = trie[tmp].mx;
evts[l-1].push_back(-i);
evts[r].push_back(i);
}
}
trie.clear();
trie.push_back(node());
foru(i, 1, n) {
reverse(all(s[i]));
add(s[i], i);
fore(j, evts[i]) {
if (j < 0) {
int tmp = get(q[-j]);
if (tmp != -1) ret[-j] -= trie[tmp].cnt;
}
else {
int tmp = get(q[j]);
if (tmp != -1) ret[j] += trie[tmp].cnt;
}
}
}
foru(i, 1, m) {
cout << ret[i] << "\n";
}
}
