#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MASK(i) (1LL << (i))
const int mod1 = 1035972859;
const int mod2 = 1704760909;
const int base = 256;
struct hashing
{
int mod;
vector<int> h, p, inv;
hashing() {}
hashing(int mod, string s)
{
int n = s.length();
this->mod = mod;
h.resize(n);
p.resize(n);
inv.resize(n);
h[0] = s[0];
p[0] = 1;
for (int i = 1; i < n; i++)
{
p[i] = (p[i - 1] * base) % mod;
h[i] = (h[i - 1] + s[i] * p[i]) % mod;
}
inv[n - 1] = power(p[n - 1], mod - 2);
for (int i = n - 2; i >= 0; i--) inv[i] = (inv[i + 1] * base) % mod;
reverse(s.begin(), s.end());
}
int power(int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1) ans = (ans * a) % mod;
(a *= a) %= mod;
b >>= 1;
}
return ans;
}
int get(int l, int r)
{
if (l > r) return 0;
return l ? ((h[r] - h[l - 1] + mod) * inv[l]) % mod : h[r];
}
bool same(int l1, int r1, int l2, int r2)
{
return get(l1, r1) == get(l2, r2);
}
};
int pos[256];
struct Trie
{
Trie* child[4];
vector<int> pos;
Trie()
{
for (int i = 0; i < 4; i++) child[i] = NULL;
}
};
Trie* p = new Trie();
void update(string s, int k)
{
auto t = p;
for (char c : s)
{
if (t->child[pos[c]] == NULL) t->child[pos[c]] = new Trie();
t = t->child[pos[c]];
t->pos.push_back(k);
}
}
int get(string s, int l, int r)
{
if (l > r) return 0;
auto t = p;
for (char c : s)
{
if (t->child[pos[c]] == NULL) return 0;
t = t->child[pos[c]];
}
return upper_bound(t->pos.begin(), t->pos.end(), r) - lower_bound(t->pos.begin(), t->pos.end(), l);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
pos['A'] = 0;
pos['C'] = 1;
pos['G'] = 2;
pos['U'] = 3;
int n, nq;
cin >> n >> nq;
vector<string> v(n);
for (string& s : v) cin >> s;
vector<hashing> h1, h2;
for (string s : v) h1.push_back(hashing(mod1, s)), h2.push_back(hashing(mod2, s));
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
if (h1[i].h.back() == h1[j].h.back() && h2[i].h.back() == h2[j].h.back()) return false;
if (v[i].length() < v[j].length())
{
if (h1[i].h.back() == h1[j].get(0, v[i].length() - 1) && h2[i].h.back() == h2[j].get(0, v[i].length() - 1)) return true;
int l = -1, r = v[i].length();
while (r - l > 1)
{
int m = (l + r) >> 1;
if (h1[i].h[m] == h1[j].h[m] && h2[i].h[m] == h2[j].h[m]) l = m;
else r = m;
}
return v[i][l + 1] < v[j][l + 1];
}
else
{
if (h1[j].h.back() == h1[i].get(0, v[j].length() - 1) && h2[j].h.back() == h2[i].get(0, v[j].length() - 1)) return false;
int l = -1, r = v[j].length();
while (r - l > 1)
{
int m = (l + r) >> 1;
if (h1[i].h[m] == h1[j].h[m] && h2[i].h[m] == h2[j].h[m]) l = m;
else r = m;
}
return v[i][l + 1] < v[j][l + 1];
}
});
for (int i = 0; i < n; i++)
{
string s = v[ord[i]];
reverse(s.begin(), s.end());
update(s, i);
}
for (int _ = 0; _ < nq; _++)
{
string s, suf;
cin >> s >> suf;
hashing hs1(mod1, s), hs2(mod2, s);
int low, high;
{
int l = -1, r = n;
while (r - l > 1)
{
int m = (l + r) >> 1;
int left = -1, right = min(s.length(), v[ord[m]].length());
while (right - left > 1)
{
int mid = (left + right) >> 1;
if (h1[ord[m]].h[mid] == hs1.h[mid] && h2[ord[m]].h[mid] == hs2.h[mid]) left = mid;
else right = mid;
}
if (left + 1 == min(s.length(), v[ord[m]].length()))
{
if (s.length() <= v[ord[m]].length()) r = m;
else l = m;
}
else
{
if (s[left + 1] > v[ord[m]][left + 1]) l = m;
else r = m;
}
}
low = r;
}
{
int l = -1, r = n;
while (r - l > 1)
{
int m = (l + r) >> 1;
int left = -1, right = min(s.length(), v[ord[m]].length());
while (right - left > 1)
{
int mid = (left + right) >> 1;
if (h1[ord[m]].h[mid] == hs1.h[mid] && h2[ord[m]].h[mid] == hs2.h[mid]) left = mid;
else right = mid;
}
if (left + 1 == min(s.length(), v[ord[m]].length()))
{
l = m;
}
else
{
if (s[left + 1] > v[ord[m]][left + 1]) l = m;
else r = m;
}
}
high = l;
}
/*cout << low << ' ' << high << '\n';
for (int i = low; i <= high; i++) cout << v[ord[i]] << ' ';
cout << '\n';*/
reverse(suf.begin(), suf.end());
cout << get(suf, low, high) << '\n';
}
return 0;
}
