/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
using namespace std;
const int maxn = 1e5 + 10 , Maxn = 1e5 + 10, lg = 22;
const int mod = 22777;
const ll inf = 1e18 + 10;
string s[maxn] , p[maxn] , q[maxn];
int32_t main(){
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n , m;
cin >> n >> m;
for(int i = 0 ; i < n ; i++)
cin >> s[i];
for(int i = 0 ; i < m ; i++){
cin >> p[i] >> q[i];
reverse(q[i].begin() , q[i].end());
}
int l1[maxn] , r1[maxn];
sort(s , s+n);
vector<pair<string , int>>v;
for(int i = 0 ; i < m ; i++){
l1[i] = lower_bound(s , s + n , p[i]) - s;
p[i][p[i].size() - 1]++;
r1[i] = lower_bound(s , s + n , p[i]) - s;
}
for(int i = 0 ; i < n ; i++){
reverse(s[i].begin() , s[i].end());
v.pb({s[i] , i});
}
sort(v.begin() , v.end());
int in[maxn];
in[n] = -1;
for(int i = 0 ; i < n ; i ++)
s[i] = v[i].first , in[v[i].second] = i;
int l2[maxn] , r2[maxn];
for(int i = 0 ; i < m ; i++){
l2[i] = lower_bound(s , s + n , q[i]) - s;
q[i][q[i].size() - 1]++;
r2[i] = lower_bound(s , s + n , q[i]) - s;
}
for(int i = 0 ; i < m ; i++){
int ans = 0;
for(int j = l1[i] ; j < r1[i] ; j++)
if(l2[i] <= in[j] && in[j] < r2[i])
ans++;
cout << ans << endl;
}
return 0;
}
