#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2000005;
int a, q;
int child[MAXN][26];
string z[1000005];
int cnt;
int mark[1000005];
int tour;
int sta[MAXN], fin[MAXN], ver[MAXN];
vector<tuple<int,int,int>> m;
const int mod1 = 1000000007;
const int mod2 = 1000000009;
const int base1 = 31;
const int base2 = 37;
bool cmpHash(const tuple<int,int,int>& A, const tuple<int,int,int>& B) {
if (get<0>(A) != get<0>(B))
return get<0>(A) < get<0>(B);
if (get<1>(A) != get<1>(B))
return get<1>(A) < get<1>(B);
return get<2>(A) < get<2>(B);
}
void add(const string& s, int pos){
int k = 0;
for (char c : s){
int idx = c - 'A';
if (!child[k][idx]) {
child[k][idx] = ++cnt;
}
k = child[k][idx];
}
mark[pos] = k;
}
void dfs(int k){
sta[k] = ++tour;
ver[tour] = k;
for (int i = 0; i < 26; i++){
if (child[k][i]) dfs(child[k][i]);
}
fin[k] = tour;
}
int get(const string& s, int h1, int h2){
int k = 0;
for (char c : s){
int idx = c - 'A';
if (!child[k][idx]) return 0;
k = child[k][idx];
}
int L = sta[k], R = fin[k];
auto leftIt = lower_bound(m.begin(), m.end(),
make_tuple(h1, h2, L),
[](auto &A, auto &B){
if (get<0>(A)!=get<0>(B)) return get<0>(A)<get<0>(B);
if (get<1>(A)!=get<1>(B)) return get<1>(A)<get<1>(B);
return get<2>(A)<get<2>(B);
});
auto rightIt = upper_bound(m.begin(), m.end(),
make_tuple(h1, h2, R),
[](auto &A, auto &B){
if (get<0>(A)!=get<0>(B)) return get<0>(A)<get<0>(B);
if (get<1>(A)!=get<1>(B)) return get<1>(A)<get<1>(B);
return get<2>(A)<get<2>(B);
});
return rightIt - leftIt;
}
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);
for (int i = 1; i <= a; i++){
int node = mark[i];
int pos = sta[node];
int h1 = 0, h2 = 0;
for (int j = (int)z[i].size() - 1; j >= 0; j--){
int v = z[i][j] - 'A' + 1;
h1 = (h1 * base1 + v) % mod1;
h2 = (h2 * base2 + v) % mod2;
m.emplace_back(h1, h2, pos);
}
}
sort(m.begin(), m.end(), cmpHash);
while (q--){
string s, t;
cin >> s >> t;
int h1 = 0, h2 = 0;
for (int i = (int)t.size() - 1; i >= 0; i--){
int v = t[i] - 'A' + 1;
h1 = (h1 * base1 + v) % mod1;
h2 = (h2 * base2 + v) % mod2;
}
cout << get(s, h1, h2) << "\n";
}
return 0;
}
