#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000005;
const int SIGMA = 26;
int n, q;
string words[maxn];
struct TrieNode
{
int children[SIGMA];
TrieNode()
{
for (int i = 0; i < SIGMA; ++i)
{
children[i] = -1;
}
}
};
struct Trie
{
int cntNodes = 1;
TrieNode tree[maxn];
int whichNode[maxn];
void addString(const string& curr, int wordIdx)
{
int node = 1;
for (int i = 0; i < curr.size(); ++i)
{
int idx = (curr[i] - 'A');
if (tree[node].children[idx] == -1)
{
tree[node].children[idx] = ++cntNodes;
}
node = tree[node].children[idx];
}
whichNode[wordIdx] = node;
}
int tim = 1;
int in[maxn];
int out[maxn];
void dfs(int node)
{
in[node] = tim++;
for (int i = 0; i < SIGMA; ++i)
{
if (tree[node].children[i] != -1)
{
dfs(tree[node].children[i]);
}
}
out[node] = tim - 1;
}
int findString(const string& curr)
{
int node = 1;
for (int i = 0; i < curr.size(); ++i)
{
int idx = (curr[i] - 'A');
if (tree[node].children[idx] == -1)
{
return -1;
}
node = tree[node].children[idx];
}
return node;
}
};
Trie pref;
Trie suff;
// x y type idx +/-
vector<tuple<int, int, int, int, int>> queries;
int answers[maxn];
struct Fenwick
{
int tree[maxn];
int MAX;
void init(int _MAX)
{
MAX = _MAX;
fill(tree, tree + MAX + 1, 0);
}
void update(int pos, int add)
{
for (; pos <= MAX; pos += (pos & (-pos)))
{
tree[pos] += add;
}
}
int query(int pos)
{
int result = 0;
for (; pos >= 1; pos -= (pos & (-pos)))
{
result += tree[pos];
}
return result;
}
};
Fenwick bit;
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
cin >> words[i];
pref.addString(words[i], i);
reverse(words[i].begin(), words[i].end());
suff.addString(words[i], i);
}
pref.dfs(1);
suff.dfs(1);
for (int i = 1; i <= n; ++i)
{
int x = pref.in[pref.whichNode[i]];
int y = suff.in[suff.whichNode[i]];
queries.push_back({x, y, 0, -1, -1});
}
bit.init(maxn - 1);
for (int i = 1; i <= q; ++i)
{
string word1, word2;
cin >> word1 >> word2;
reverse(word2.begin(), word2.end());
int prefNode = pref.findString(word1);
int suffNode = suff.findString(word2);
int inp = (prefNode == -1 ? -1 : pref.in[prefNode]);
int outp = (prefNode == -1 ? -1 : pref.out[prefNode]);
int ins = (suffNode == -1 ? -1 : suff.in[suffNode]);
int outs = (suffNode == -1 ? -1 : suff.out[suffNode]);
//cout << i << " :: " << inp << " " << outp << " " << ins << " " << outs << endl;
queries.push_back({outp, outs, 1, i, +1});
queries.push_back({inp - 1, outs, 1, i, -1});
queries.push_back({outp, ins - 1, 1, i, -1});
queries.push_back({inp - 1, ins - 1, 1, i, +1});
}
sort(queries.begin(), queries.end());
for (auto [x, y, type, idx, coeff] : queries)
{
if (type == 0)
{
if (y != -1) bit.update(y, +1);
}
else
{
if (x == -1 || y == -1) answers[idx] = 0;
else answers[idx] += coeff * bit.query(y);
}
}
for (int i = 1; i <= q; ++i)
{
cout << answers[i] << "\n";
}
return 0;
}
