#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, q;
int child[2000005][26];
string z[100005];
int cnt, markNode[1000005], sta[1000005], finNode[1000005], tour;
vector<pair<long long, int>> allPairs;
const int BASE = 31;
void add(const string &s, int idx)
{
int u = 0;
for (char c : s)
{
int d = c - 'A';
if (!child[u][d])
child[u][d] = ++cnt;
u = child[u][d];
}
markNode[idx] = u;
}
void dfs(int u)
{
sta[u] = ++tour;
for (int d = 0; d < 26; ++d)
{
int v = child[u][d];
if (v)
dfs(v);
}
finNode[u] = tour;
}
int getCount(const string &pre, long long hq)
{
int u = 0;
for (char c : pre)
{
int d = c - 'A';
if (!child[u][d])
return 0;
u = child[u][d];
}
int L = sta[u], R = finNode[u];
auto lo = lower_bound(allPairs.begin(), allPairs.end(), make_pair(hq, -1LL));
auto hi = upper_bound(allPairs.begin(), allPairs.end(), make_pair(hq, (int)1e9));
if (lo == hi)
return 0;
auto it1 = lower_bound(lo, hi, make_pair(hq, L));
auto it2 = upper_bound(lo, hi, make_pair(hq, R));
return it2 - it1;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> q;
for (int i = 1; i <= a; ++i)
{
cin >> z[i];
add(z[i], i);
}
dfs(0);
long long totalLen = 0;
for (int i = 1; i <= a; ++i)
totalLen += z[i].size();
allPairs.reserve(totalLen);
for (int i = 1; i <= a; ++i)
{
long long h = 0;
int pos = sta[markNode[i]];
for (int j = z[i].size() - 1; j >= 0; --j)
{
h = h * BASE + (z[i][j] - 'A' + 1);
allPairs.emplace_back(h, pos);
}
}
sort(allPairs.begin(), allPairs.end());
while (q--)
{
string P, Q;
cin >> P >> Q;
long long hq = 0;
for (int j = Q.size() - 1; j >= 0; --j)
hq = hq * BASE + (Q[j] - 'A' + 1);
cout << getCount(P, hq) << '\n';
}
return 0;
}
