#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20;
const ll MAXN = 1e5 + 100;
int no[MAXN];
int last_given = 0;
struct Node {
Node *to[4];
vector<int> v;
vector<int> last;
void srt() {
sort(v.begin(), v.end());
for (int i = 0; i < 4; i++) {
if (to[i] != NULL)
to[i]->srt();
}
}
void dfs() {
for (auto u : last) {
last_given++;
no[u] = last_given;
}
for (int i = 0; i < 4; i++) {
if (to[i] != NULL)
to[i]->dfs();
}
}
};
int c(char ch) {
if (ch == 'A')
return 0;
if (ch == 'G')
return 1;
if (ch == 'C')
return 2;
return 3;
}
vector<string> vs;
int main() {
int N, M;
cin >> N >> M;
Node *root = new Node();
Node *root_rev = new Node();
vs = vector<string>(N+1);
for (int i = 1; i <= N; i++) {
cin >> vs[i];
Node *now = root;
now->v.push_back(i);
for (auto u : vs[i]) {
int q = c(u);
if (now->to[q] == NULL)
now->to[q] = new Node();
now = now->to[q];
now->v.push_back(i);
}
now->last.push_back(i);
}
root->dfs();
for (int i = 1; i <= N; i++) {
int q = no[i];
Node *now = root_rev;
now->v.push_back(q);
int len = vs[i].length();
for (int j = len-1; j >= 0; j--) {
int p = c(vs[i][j]);
if (now->to[p] == NULL)
now->to[p] = new Node();
now = now->to[p];
now->v.push_back(q);
}
}
root = new Node();
for (int i = 1; i <= N; i++) {
int q = no[i];
Node *now = root;
now->v.push_back(q);
for (auto u : vs[i]) {
int p = c(u);
if (now->to[p] == NULL)
now->to[p] = new Node();
now = now->to[p];
now->v.push_back(q);
}
}
root->srt();
root_rev->srt();
while (M--) {
string pref, suff;
cin >> pref >> suff;
reverse(suff.begin(), suff.end());
Node *now = root;
for (auto u : pref) {
int q = c(u);
if (now->to[q] == NULL)
now->to[q] = new Node();
now = now->to[q];
}
int mn = -1, mx = -1;
if (now->v.size()) {
mn = now->v.front();
mx = now->v.back();
}
now = root_rev;
for (auto u : suff) {
int q = c(u);
if (now->to[q] == NULL)
now->to[q] = new Node();
now = now->to[q];
}
cout << upper_bound(now->v.begin(), now->v.end(), mx) - lower_bound(now->v.begin(), now->v.end(), mn) << "\n";
}
}
