#include <array>
#include <typeinfo>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)
#define sz(x) int((x).size())
#define lb(x...) lower_bound(x)
#define ub(x...) upper_bound(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define eb(x...) emplace_back(x)
constexpr int A = 4;
map<char, int> cmp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
struct T {
array<T*, A> nxt;
vector<int> idx;
T() { fill(all(nxt), nullptr); }
template<class it>
void insert(it st, it en, int i) {
idx.eb(i);
if (st == en) return;
auto &x = nxt[cmp[*st]];
if (!x) x = new T();
x->insert(next(st), en, i);
}
template<class it>
int query(it st, it en, int l, int r) { // [l, r)
if (st == en)
return lb(all(idx), r) - lb(all(idx), l);
auto &x = nxt[cmp[*st]];
return x ? x->query(next(st), en, l, r) : 0;
}
} t;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> s(n);
rep(i, 0, n) cin >> s[i];
sort(all(s));
rep(i, 0, n) t.insert(rall(s[i]), i);
while (m--) {
string p, q; cin >> p >> q;
int l = lb(all(s), p) - begin(s);
++p.back();
int r = ub(all(s), p) - begin(s);
cout << t.query(rall(q), l, r) << '\n';
}
}
