#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define lc (v<<1)
#define rc (lc|1)
#define pll pair<string, int>
#define ppll pair<int,pll>
#define fr first
#define sc second
#define low lower_bound
#define upp upper_bound
#define pb push_back
#define endl '\n';
#define mp make_pair
const int mxn = 1e5+10;
//const ll inf = 1e18;
const int mod = 1e9+7;
ll gcd(ll a, ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a, ll b){return (a/gcd(a, b))*b;}
ll pw(ll x, ll y) {
ll r = 1;
while (y) {
if (y & 1) r = 1LL * r * x % mod;
x = 1LL * x * x % mod;
y >>= 1;
}
return r;
}
int n, m;
string s[mxn],p[mxn],q[mxn];
ll a[mxn],b[mxn],c[mxn],d[mxn],ys[mxn];
vector <ll> dat[mxn<<1];
ll res(ll c,ll d,ll k){
return low(dat[k].begin(), dat[k].end(),d)-low(dat[k].begin(), dat[k].end(),c);
}
int main(){
cin >> n >> m;
vector<pll>v;
for(int i=0; i<n; i++)cin >> s[i];
for(int i=0; i<m; i++)cin >> p[i] >> q[i];
sort(s,s+n);
for(int i=0; i<m; i++){
a[i]=low(s,s+n,p[i])-s;
p[i][p[i].size()-1]++;
b[i]=low(s,s+n,p[i])-s;
}
for(int i=0; i<n; i++){
for(int j=0; j<s[i].size()/2; j++)
swap(s[i][j],s[i][s[i].size()-1-j]);
v.pb(mp(s[i],i));
}
sort(v.begin(),v.end());
for(int i=0; i<n; i++)ys[v[i].sc] = i;
for(int i=0; i<n; i++)s[i] = v[i].fr;
for(int i=0; i<m; i++){
for(int j=0; j<q[i].size()/2; j++)
swap(q[i][j],q[i][q[i].size()-1-j]);
c[i]=low(s,s+n,q[i])-s;
q[i][q[i].size()-1]++;
d[i]=low(s,s+n,q[i])-s;
}
for(int i=0; i<n; i++){
for(ll x = i+mxn; x; x>>=1){
dat[x].pb(ys[i]);
}
}
for(int i=0; i<mxn<<1; i++)
sort(dat[i].begin(),dat[i].end());
for(int i=0; i<m; i++){
ll ans = 0, l = a[i]+mxn, r = b[i]+mxn;
for(; l<r; l>>=1, r>>=1){
if(l&1)ans+=res(c[i],d[i],l++);
if(r&1)ans+=res(c[i],d[i],--r);
}
cout << ans << endl;
}
return 0;
}
