#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif
#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;
vi to_v(string S) {
vi v(sz(S));
for (int i = 0; i < sz(S); i++) v[i] = S[i] == 'A' ? 0 : S[i] == 'G' ? 1 : S[i] == 'C' ? 2 : 3;
return v;
}
struct node {
int mn, mx, cnt;
node *kids[4];
node() {
mn = INT_MAX, mx = -1;
cnt = 0;
for (int i : {0, 1, 2, 3}) kids[i] = NULL;
}
void add(int id) {
mn = min(mn, id);
mx = max(mx, id);
cnt++;
}
} *root;
void ins(const vi s, int id) {
node *v = root;
for (int c : s) {
if (v->kids[c] == NULL) v->kids[c] = new node();
v = v->kids[c];
v->add(id);
}
}
ar<int, 3> qry(const vi s) {
node *v = root;
for (int c : s) {
if (v->kids[c] == NULL) return {-1, -1, 0};
v = v->kids[c];
}
return {v->mn, v->mx, v->cnt};
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int N, M;
cin >> N >> M;
vector<vi> v(N);
for (int i = 0; i < N; i++) {
string s; cin >> s;
v[i] = to_v(s);
}
sort(all(v));
root = new node();
for (int i = 0; i < N; i++) ins(v[i], i);
vi ans(M);
vector<vi> u(M);
vector<vector<pi>> todo(N);
for (int i = 0; i < M; i++) {
string s, t; cin >> s >> t;
auto [l, r, c] = qry(to_v(s));
if (!c) continue;
u[i] = to_v(t);
reverse(all(u[i]));
todo[r].push_back({i, 1});
if (l) todo[l - 1].push_back({i, -1});
}
root = new node();
for (int i = 0; i < N; i++) {
reverse(all(v[i]));
ins(v[i], i);
for (auto [j, c] : todo[i]) ans[j] += c * qry(u[j])[2];
}
for (int x : ans) cout << x << '\n';
}
