#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
const ll MAXN = 1e5+5;
string s[MAXN];
pair <string,ll> r[MAXN];
ll ar[MAXN];
struct wavelet {
wavelet *l, *r;
ll ini,fin;
vector <ll> v,in;
wavelet (ll INI, ll FIN) {
ini = INI;
fin = FIN;
}
void setup(ll num[]) {
if (ini==fin) return;
l = new wavelet(ini,(ini+fin)/2);
r = new wavelet((ini+fin)/2+1,fin);
for (int i=0;i<in.size();i++) {
if (num[in[i]]<=(ini+fin)/2) {
if (!v.empty()) v.push_back(v[v.size()-1]+1);
else v.push_back(1);
l->in.push_back(in[i]);
}
else {
if (!v.empty()) v.push_back(v[v.size()-1]);
else v.push_back(0);
r->in.push_back(in[i]);
}
}
l->setup(num);
r->setup(num);
return;
}
ll query(ll L, ll R, ll a, ll b) {
if (ini>b || a>fin || R<L) return 0;
if (a<=ini && fin<=b) return R-L+1;
ll aux = 0;
if (L>0) aux += l->query(v[L-1],v[R]-1,a,b);
else aux += l->query(0,v[R]-1,a,b);
if (L>0) aux += r->query(L-v[L-1],R-v[R],a,b);
else aux += r->query(L,R-v[R],a,b);
return aux;
}
};
ll bin_pre1(ll ini, ll fin, string &pre) { //devuelve el primero igual o mayor
if (ini==fin) return ini;
if (pre>s[(ini+fin)/2]) return bin_pre1((ini+fin)/2+1,fin,pre);
else return bin_pre1(ini,(ini+fin)/2,pre);
}
ll bin_pre2(ll ini, ll fin, string &pre) { //devuelve el primero mas grande
if (ini==fin) return ini;
if (pre>=(s[(ini+fin)/2].substr(0,pre.size()))) return bin_pre2((ini+fin)/2+1,fin,pre);
else return bin_pre2(ini,(ini+fin)/2,pre);
}
ll bin_suf1(ll ini, ll fin, string &pre) { //devuelve el primero igual o mayor
if (ini==fin) return ini;
if (pre>r[(ini+fin)/2].f) return bin_suf1((ini+fin)/2+1,fin,pre);
else return bin_suf1(ini,(ini+fin)/2,pre);
}
ll bin_suf2(ll ini, ll fin, string &pre) { //devuelve el primero mas grande
if (ini==fin) return ini;
if (pre>=(r[(ini+fin)/2].f.substr(0,pre.size()))) return bin_suf2((ini+fin)/2+1,fin,pre);
else return bin_suf2(ini,(ini+fin)/2,pre);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,q,a,b,c,d;
string pre,suf;
cin>>n>>q;
for (int i=0;i<n;i++) cin>>s[i];
sort(s,s+n);
for (int i=0;i<n;i++) {
r[i].f = s[i];
reverse(r[i].f.begin(),r[i].f.end());
r[i].s = i;
}
sort(r,r+n);
for (int i=0;i<n;i++) ar[r[i].s] = i;
wavelet *wave = new wavelet(0,MAXN);
for (int i=0;i<n;i++) wave->in.push_back(i);
wave->setup(ar);
while (q--) {
cin>>pre>>suf;
reverse(suf.begin(),suf.end());
a = bin_suf1(0,n,suf);
b = bin_suf2(0,n,suf)-1;
c = bin_pre1(0,n,pre);
d = bin_pre2(0,n,pre)-1;
cout<<wave->query(c,d,a,b)<<'\n';
}
return 0;
}
