#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define REP(i, n) for(int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for(int i = (n); i >= 1; i--)
#define FOR(i, k, n) for(int i = (k), _n = (n); i <= _n; ++i)
#define FOV(i, k, n) for(int i = (k), _n = (n); i >= _n; --i)
#define MASK(i) (1LL << (i))
#define NUM_BIT(i) (__builtin_popcountll(i))
#define BIT(i, mask) ((mask & MASK(i)) != 0)
#define OFF(i, mask) (mask ^ MASK(i))
#define ON(i, mask) (mask | MASK(i))
const int BS = 450;
const int LOG = 18;
const int NMOD = 5;
const int NBASE = 3;
const int base[] = {0, 29, 31};
const int MOD[] = {0, (int)1e9 + 7, (int)998244353, (int)1e9 + 5277};
const int hx[] = {0, 0, 0, 1, -1};
const int hy[] = {0, -1, 1, 0, 0};
const int mod = 1e9 + 22071997;
const int MAXS = 1e4 + 5;
const int MAXN = 1e5 + 5;
int n, m, cur;
vector<string> s;
int w(char s) {
if (s == 'A') return 0;
if (s == 'U') return 1;
if (s == 'G') return 2;
if (s == 'X') return 3;
}
struct Node {
Node* child[4];
int ex;
int l, r;
vector<int> id;
Node() {
memset(child, NULL, sizeof child);
ex = 0;
l = r = 0;
id.clear();
}
};
Node* root = new Node();
Node* rootpre = new Node();
Node* rootsuf = new Node();
void add(string s) {
Node* k = root;
FOR (i, 0, s.size() - 1) {
if (k -> child[w(s[i])] == NULL) k -> child[w(s[i])] = new Node();
k = k -> child[w(s[i])];
}
k -> ex++;
}
void dfs(Node* k, string t) {
if (k -> child[0] != NULL) dfs(k -> child[0], t + 'A');
if (k -> child[1] != NULL) dfs(k -> child[1], t + 'U');
if (k -> child[2] != NULL) dfs(k -> child[2], t + 'G');
if (k -> child[3] != NULL) dfs(k -> child[3], t + 'X');
while (k -> ex--) s.pb(t);
}
void addpre(string s, int id) {
Node* k = rootpre;
FOR (i, 0, s.size() - 1) {
if (k -> child[w(s[i])] == NULL) {
k -> child[w(s[i])] = new Node();
k -> child[w(s[i])] -> l = id;
k -> child[w(s[i])] -> r = id;
}
else k -> child[w(s[i])] -> r++;
k = k -> child[w(s[i])];
}
}
void addsuf(string s, int id) {
reverse(s.begin(), s.end());
Node* k = rootsuf;
FOR (i, 0, s.size() - 1) {
if (k -> child[w(s[i])] == NULL) k -> child[w(s[i])] = new Node();
k = k -> child[w(s[i])];
k -> id.pb(id);
}
}
pii getpre(string s) {
Node* k = rootpre;
FOR (i, 0, s.size() - 1) {
if (k -> child[w(s[i])] == NULL) return {0, 0};
k = k -> child[w(s[i])];
}
return {k -> l, k -> r};
}
int getsuf(string t, string s) {
pii p = getpre(t);
int l = p.fi;
int r = p.se;
if (!l) return 0;
Node* k = rootsuf;
reverse(s.begin(), s.end());
FOR (i, 0, s.size() - 1) {
if (k -> child[w(s[i])] == NULL) return 0;
k = k -> child[w(s[i])];
}
vector<int> ve = k -> id;
return (upper_bound(ve.begin(), ve.end(), r) - lower_bound(ve.begin(), ve.end(), l));
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("threejug.inp", "r", stdin);
// freopen("threejug.out", "w", stdout);
cin >> n >> m;
REP (i, n) {
string x;
cin >> x;
add(x);
}
s.pb("nger");
dfs(root, "");
REP (i, n) {
addpre(s[i], i);
addsuf(s[i], i);
}
REP (i, m) {
string x, y;
cin >> x >> y;
cout << getsuf(x, y) << endl;
}
return 0;
}
