#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], tries;
vector<int> ids[40*N];
int nxt[40*N][4];
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);
}
int main() {
P[0] = 1;
for(int i = 1; i < N; ++i) {
P[i] = (long long)P[i - 1] * p % MOD;
}
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);
for(int i = 1; i <= n; ++i) {
int hash = 0;
reverse(s[i].begin(), s[i].end());
add(s[i], i);
reverse(s[i].begin(), s[i].end());
}
for(int i = 1; i <= m; ++i) {
string p, q; cin >> p >> q;
int L = n+1, R = 0;
L = find_first(p);
if(!is_prefix(p, s[L])) {
cout << "0\n";
continue;
}
R = find_last(L, p);
if(L > R) {
cout << "0\n";
continue;
}
reverse(q.begin(), q.end());
cout << get(q, L, R) << '\n';
}
}
