#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define bit(mask, i) ((mask >> i) & 1)
#define el '\n'
#define F first
#define S second
template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};
const int N = 1e5 + 5;
const int MAX = 2e6 + 5;
int n, m, curNode, pw[nMOD][N], hashQ1[N], res[N], ti[MAX], to[MAX], timeDfs;
string s[N], p[N], q[N];
pair<int, int> hashQ[N];
vector<int> at[N], adj[MAX];
vector<pair<int, int>> comp;
struct query {
int idHash, idQuery;
bool operator < (const query &other) const {
return idHash < other.idHash;
}
} Q[N];
struct node {
node *child[26];
int id, h, cnt;
node() {
for (int i = 0; i < 26; ++i) child[i] = nullptr;
id = h = cnt = 0;
}
};
node *root = new node();
void add(string &x) {
node *u = root;
for (auto c: x) {
int k = c - 'A';
if (u -> child[k] == nullptr) {
u -> child[k] = new node();
u -> child[k] -> id = ++curNode;
u -> child[k] -> h = u -> h + 1;
adj[u -> id].push_back(u -> child[k] -> id);
}
u = u -> child[k];
u -> cnt++;
}
}
void trav(string &x) {
vector<char> path;
node *u = root;
for (auto c: x) {
int k = c - 'A';
path.push_back(c);
u = u -> child[k];
}
pair<int, int> H = make_pair(0, 0);
int len = 0;
reverse(path.begin(), path.end());
for (auto c: path) {
H.F = (1LL * (c - 'A' + 1) * pw[0][len] + H.F) % mods[0];
H.S = (1LL * (c - 'A' + 1) * pw[1][len] + H.S) % mods[1];
int pos = lower_bound(comp.begin(), comp.end(), H) - comp.begin();
if (pos < (int) comp.size() && comp[pos] == H)
at[pos + 1].push_back(u -> id);
len++;
}
}
void precalc() {
for (int i = 0; i < nMOD; ++i) {
pw[i][0] = 1;
for (int j = 1; j < N; ++j)
pw[i][j] = 1LL * pw[i][j - 1] * base % mods[i];
}
}
void calcHash(string &x, pair<int, int> &H) {
int len = (int) x.size();
for (int i = 1; i <= len; ++i) {
H.F = (1LL * H.F * base + x[i - 1] - 'A' + 1) % mods[0];
H.S = (1LL * H.S * base + x[i - 1] - 'A' + 1) % mods[1];
}
}
void compressHashQ() {
for (int i = 1; i <= m; ++i)
comp.push_back(hashQ[i]);
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
for (int i = 1; i <= m; ++i)
hashQ1[i] = lower_bound(comp.begin(), comp.end(), hashQ[i]) - comp.begin() + 1;
}
void dfs(int u) {
ti[u] = ++timeDfs;
for (int v: adj[u])
dfs(v);
to[u] = timeDfs;
}
struct BIT {
int bit[MAX];
void update(int id, int v) {
for (; id <= curNode; id += id & -id)
bit[id] += v;
}
int get(int id) {
int res = 0;
for (; id > 0; id -= id & -id)
res += bit[id];
return res;
}
int getRange(int l, int r) {
if (l > r) return 0;
return get(r) - get(l - 1);
}
} bit;
void updateAns(int i) {
node *u = root;
for (auto c: p[i]) {
int k = c - 'A';
if (u -> child[k] == nullptr) return;
u = u -> child[k];
}
res[i] = bit.getRange(ti[u -> id], to[u -> id]);
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
add(s[i]);
}
precalc();
for (int i = 1; i <= m; ++i) {
cin >> p[i] >> q[i];
calcHash(q[i], hashQ[i]);
}
compressHashQ();
for (int i = 1; i <= n; ++i)
trav(s[i]);
dfs(0);
for (int i = 1; i <= m; ++i) {
Q[i].idHash = hashQ1[i];
Q[i].idQuery = i;
}
sort(Q + 1, Q + 1 + m);
int ptr = 1;
curNode++;
while (ptr <= m) {
for (int x: at[Q[ptr].idHash])
bit.update(ti[x], 1);
int j = ptr;
updateAns(Q[ptr].idQuery);
while (j < m && Q[j + 1].idHash == Q[j].idHash) {
updateAns(Q[++j].idQuery);
}
for (int x: at[Q[ptr].idHash])
bit.update(ti[x], -1);
ptr = j + 1;
}
for (int i = 1; i <= m; ++i)
cout << res[i] << el;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!MULTI) solve();
else {
int test; cin >> test;
while (test--) solve();
}
return 0;
}
