#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e5 + 12, MX = 2e6 + 12;
const ll INF = 1e18;
unordered_map<char, int> bor1[MX], bor2[MX];
vector< int > mark[MX], term[MX];
int ptr1 = 1, ptr2 = 1, n, m;
int tin[MX], tout[MX], timer;
string t[N];
void dfs(int v){
tin[v] = ++timer;
for(int id: mark[v]){
int u = 1;
for(int j = 0;j < (int)t[id].size();j++){
if(!bor1[u].count(t[id][j]))
bor1[u][t[id][j]] = ++ptr1;
u = bor1[u][t[id][j]];
term[u].push_back(v);
}
}
for(pair<char, int> to: bor2[v]){
dfs(to.Y);
}
tout[v] = timer;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> t[i];
int v = 1;
for(int j = (int)t[i].size() - 1;j >= 0;j--){
if(!bor2[v].count(t[i][j]))
bor2[v][t[i][j]] = ++ptr2;
v = bor2[v][t[i][j]];
} mark[v].push_back(i);
}
dfs(1);
for(int i = 1;i <= m;i++){
string s1, s2;
cin >> s1 >> s2;
int v = 1, good = 1;
for(int j = (int)s2.size() - 1;j >= 0;j--){
if(!bor2[v].count(s2[j])){
good = 0;
break;
}
v = bor2[v][s2[j]];
}
int u = 1;
for(int j = 0;j < (int)s1.size();j++){
if(!bor1[u].count(s1[j])){
good = 0;
break;
}
u = bor1[u][s1[j]];
}
int ans = 0;
if(good){
int tl = 1, tr = term[u].size(), tp1 = term[u].size() + 1;
while(tl <= tr){
int tm = (tl + tr) / 2;
if(tin[v] <= tin[term[u][tm - 1]]){
tr = tm - 1, tp1 = tm;
}
else{
tl = tm + 1;
}
}
tl = 1, tr = term[u].size(); int tp2 = term[u].size();
while(tl <= tr){
int tm = (tl + tr) / 2;
if(tout[v] < tin[term[u][tm - 1]]){
tr = tm - 1;
}
else{
tl = tm + 1, tp2 = tm;
}
}
ans = tp2 - tp1 + 1;
}
cout << ans << "\n";
}
}
