#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
namespace Trie1
{
struct Node
{
int32_t child[26]{};
int l = 100000;
int r = -1;
};
Node nodes[2000001];
int cur = 1;
inline int try_push_back(int x, int c, int idx)
{
if (!nodes[x].child[c])
nodes[x].child[c] = cur++;
int y = nodes[x].child[c];
nodes[y].l = min(nodes[y].l, idx);
nodes[y].r = max(nodes[y].r, idx);
return y;
}
void insertString(string &s, int idx)
{
int cur = 0;
for (auto &i : s)
cur = try_push_back(cur, i - 'A', idx);
}
pair<int, int> getRange(string &s)
{
int cur = 0;
for (auto &i : s)
{
cur = nodes[cur].child[i - 'A'];
if (!cur)
return {100000, -1};
}
return {nodes[cur].l, nodes[cur].r};
}
}; // namespace Trie1
namespace Trie2
{
struct Node
{
int32_t child[26]{};
};
Node nodes[2000001];
vector<pair<int, int>> s_cnt[2000001];
int cur = 1;
inline int try_push_back(int x, int c, int idx)
{
if (!nodes[x].child[c])
nodes[x].child[c] = cur++;
int y = nodes[x].child[c];
s_cnt[y].push_back({idx, (s_cnt[y].size() ? s_cnt[y].back().second : 0) + 1});
return y;
}
void insertString(string &s, int idx)
{
int cur = 0;
for (auto &i : s)
cur = try_push_back(cur, i - 'A', idx);
}
int getnStrings(string &s, int idx1, int idx2)
{
if (idx1 > idx2)
return 0;
int cur = 0;
for (auto &i : s)
{
cur = nodes[cur].child[i - 'A'];
if (!cur)
return 0;
}
int xc = upper_bound(s_cnt[cur].begin(), s_cnt[cur].end(), pair<int, int>{idx2, 100000}) - 1 - s_cnt[cur].begin();
int yc = lower_bound(s_cnt[cur].begin(), s_cnt[cur].end(), pair<int, int>{idx1, 0}) - 1 - s_cnt[cur].begin();
if (xc < 0)
return 0;
if (yc < 0)
return s_cnt[cur][xc].second;
return s_cnt[cur][xc].second - s_cnt[cur][yc].second;
}
}; // namespace Trie2
void Yoshi()
{
int n, q;
cin >> n >> q;
vector<string> sp(n);
for (auto &i : sp)
cin >> i;
sort(sp.begin(), sp.end());
for (int i = 0; i < n; i++)
Trie1::insertString(sp[i], i);
for (int i = 0; i < n; i++)
reverse(sp[i].begin(), sp[i].end()), Trie2::insertString(sp[i], i);
for (int i = 0; i < q; i++)
{
string s, t;
cin >> s >> t;
reverse(t.begin(), t.end());
auto [a, b] = Trie1::getRange(s);
cout << Trie2::getnStrings(t, a, b) << endl;
}
}
signed main()
{
#ifndef yoshi_likes_e4
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(problem ".inp", "r"))
{
freopen(problem ".inp", "r", stdin);
freopen(problem ".out", "w", stdout);
}
#endif
init();
int t = 1;
#if multitest
cin >> t;
#endif
while (t--)
Yoshi();
}
