#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 3e6 + 2, mod = 998244353;
int n, res, numnode, m;
string s[maxn], p, q;
vector<int> ok;
struct Node
{
int child[26];
int l, r;
vector<int> v;
}node[maxn];
struct PrefixTrie
{
void add (int idx, string &s)
{
int cur = 0;
for (char c : s)
{
if (node[cur].child[c - 'A'] == 0)
{
cur = node[cur].child[c - 'A'] = ++numnode;
node[cur].l = node[cur].r = idx;
}
else
{
cur = node[cur].child[c - 'A'];
node[cur].r = idx;
}
}
}
pair<int, int> find (string &s)
{
int cur = 0;
for (char c : s)
{
if (node[cur].child[c - 'A'] == 0) return {0, 0};
cur = node[cur].child[c - 'A'];
}
return {node[cur].l, node[cur].r};
}
}ptrie;
struct SuffixTrie
{
void add (int idx, string &s)
{
int cur = 0;
for (char c : s)
{
if (node[cur].child[c - 'A'] == 0) cur = node[cur].child[c - 'A'] = ++numnode;
else cur = node[cur].child[c - 'A'];
node[cur].v.push_back(idx);
}
}
vector<int> find (string &s)
{
int cur = 0;
for (char c : s)
{
if (node[cur].child[c - 'A'] == 0) return {};
cur = node[cur].child[c - 'A'];
}
return node[cur].v;
}
}strie;
int main()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> s[i];
sort(s + 1, s + n + 1);
for (int i = 1; i <= n; i++) ptrie.add(i, s[i]);
for (int i = 1; i <= n; i++)
{
reverse(s[i].begin(), s[i].end());
strie.add(i, s[i]);
}
while (m--)
{
cin >> p >> q;
reverse(q.begin(), q.end());
auto [L, R] = ptrie.find(p);
ok = strie.find(q);
if (L == 0 || ok.empty())
{
cout << 0 << '\n';
continue;
}
ok.push_back(n + 1);
cout << upper_bound(ok.begin(), ok.end(), R) - lower_bound(ok.begin(), ok.end(), L) << '\n';
}
}
