#include "bits/stdc++.h"
using namespace std;
const int N = 2e5+10, p = 37, MOD = 1e9+7;
string s[N];
int n, m, P[N];
bool check(const string &a, const string &b) { // a >= b ? true : false
int mini = min((int)a.size(), (int)b.size());
for(int i = 0; i < mini; ++i) {
if(a[i] != b[i]) {
return a[i] > b[i];
}
}
return mini == (int)b.size();
}
bool is_prefix(const string &a, const string &b) {
if((int)a.size() > (int)b.size()) {
return false;
}
for(int i = 0; i < (int)a.size(); ++i) {
if(a[i] != b[i]) {
return false;
}
}
return true;
}
int find_first(const string &p) {
int l = 1, r = n, pos = n+1;
while(r >= l) {
int m = l + r >> 1;
if(check(s[m], p)) {
r = m - 1;
pos = m;
} else {
l = m + 1;
}
}
return pos;
}
int find_last(int start, const string &p) {
int l = start, r = n, pos = 0;
while(r >= l) {
int m = l + r >> 1;
if(is_prefix(p, s[m])) {
pos = m;
l = m + 1;
} else {
r = m - 1;
}
}
return pos;
}
int count(const vector<int> &v, int x) {
if(v.empty()) return 0;
int l = 0, r = (int)v.size()-1, pos = -1;
while(r >= l) {
int m = l + r >> 1;
if(v[m] <= x) {
pos = m;
l = m + 1;
} else {
r = m - 1;
}
}
return pos+1;
}
int count(const vector<int> &v, int L, int R) {
return count(v, R) - count(v, L-1);
}
int id[256];
struct trie {
int tries;
vector<array<int, 4>> nxt;
vector<vector<int>> ids;
trie() {}
trie(int size) {
tries = 0;
nxt = vector<array<int, 4>>(size);
ids = vector<vector<int>>(size);
}
void add(const string &s, int pos) {
int cur = 0;
for(int i = 0; i < (int)s.size(); ++i) {
if(nxt[cur][id[s[i]]] == 0) {
nxt[cur][id[s[i]]] = ++tries;
}
cur = nxt[cur][id[s[i]]];
ids[cur].push_back(pos);
}
}
int get(const string &s, int L, int R) {
int cur = 0;
for(int i = 0; i < (int)s.size(); ++i) {
cur = nxt[cur][id[s[i]]];
}
return count(ids[cur], L, R);
}
pair<int, int> get(const string &s) {
int cur = 0;
for(int i = 0; i < (int)s.size(); ++i) {
cur = nxt[cur][id[s[i]]];
}
if(ids[cur].empty()) {
return {0, 0};
}
return {ids[cur][0], ids[cur].back()};
}
};
int main() {
id['A'] = 1;
id['U'] = 2;
id['G'] = 3;
id['C'] = 4;
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> s[i];
}
sort(s+1, s+n+1);
trie t1(40*N), t2(40*N);
for(int i = 1; i <= n; ++i) {
t1.add(s[i], i);
reverse(s[i].begin(), s[i].end());
t2.add(s[i], i);
reverse(s[i].begin(), s[i].end());
}
for(int i = 1; i <= m; ++i) {
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
pair<int, int> LR = t1.get(p);
cout << t2.get(q, LR.first, LR.second) << '\n';
}
}
