#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int inf = 1e17,N = 3e5+1,MOD = 1e9+7,BL = 1000;
vi ans(N);
struct Node {
vector<pair<string,int>> Queries;
string str;
int bas = 0;
vi star;
int c[26]{};
};
Node clean;
struct Trie {
vector<Node> nds = {clean};
int ctr = 0;
void parent(int node,int p,int id) {
nds[p].c[id] = node;
}
void insert(int node, string& s,int ptr,int t) {
nds[node].star.push_back(t);
if (ptr == s.size()) {
nds[node].bas++;
if (nds[node].str.empty()) {
nds[node].str = s;
reverse(all(nds[node].str));
}
return;
}
if (!nds[node].c[s[ptr]-'A']) {
nds.push_back(clean);
parent(++ctr,node,s[ptr]-'A');
}
ptr++;
insert(nds[node].c[s[ptr-1]-'A'],s,ptr,t);
}
void insertquery(int node,string& s,string& t,int qid,int ptr) {
if (ptr == s.size()) {
nds[node].Queries.push_back({t,qid});
return;
}
if (!nds[node].c[s[ptr]-'A']) {
nds.push_back(clean);
parent(++ctr,node,s[ptr]-'A');
}
ptr++;
insertquery(nds[node].c[s[ptr-1]-'A'],s,t,qid,ptr);
}
int ask(int node,string& s,int ptr) {
if (ptr == s.size()) return node;
if (!nds[node].c[s[ptr]-'A']) return -1;
ptr++;
return ask(nds[node].c[s[ptr-1]-'A'],s,ptr);
}
} trie,trie2;
int idx(vi& v,int x) {
return upper_bound(all(v),x)-v.begin();
}
vi tin(N);
int timer = 0;
void walk(int node) {
tin[node] = timer++;
Node& nd = trie.nds[node];
//cout << "NODE" sp node sp nd.star.size() sp nd.Queries.size() << endl;
for (int i = 0;i<26;i++) if (nd.c[i]) walk(nd.c[i]);
if (!nd.str.empty()) for (int i = 0;i<nd.bas;i++) {
//cout << "INSERTING" sp nd.str sp tin[node] << endl;
trie2.insert(0,nd.str,0,tin[node]);
}
for (auto Q : nd.Queries) {
int tnode = trie2.ask(0,Q.ff,0);
if (tnode == -1) ans[Q.ss] = 0;
else ans[Q.ss] = trie2.nds[tnode].star.size()-idx(trie2.nds[tnode].star,tin[node]-1);
//cout << "ASKING" sp Q.ff sp tin[node] sp tnode sp ans[Q.ss] << '\n';
}
}
void solve() {
int n,q;
cin >> n >> q;
for (int i=1;i<=n;i++) {
string s;
cin >> s;
trie.insert(0,s,0,0);
}
for (int i=1;i<=q;i++) {
string pref,suf;
cin >> pref >> suf;
reverse(all(suf));
trie.insertquery(0,pref,suf,i,0);
}
walk(0);
for (int i=1;i<=q;i++) cout << ans[i] << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
