//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 1e5 + 7;
int Mod = 1e9 + 7;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;
int n, Q;
vector<string> vec;
string Rev (string &S) {
static string res;
res = "";
reb (i, SZ(S) - 1, 0) res += S[i];
return res;
}
struct tNode {
tNode *child[26];
vector<int> vec;
tNode () {
rep (i, 0, 25) child[i] = NULL;
}
}*proot = new tNode(), *sroot = new tNode();
void Add (tNode *cur, string S, int idx) {
iter (&id, S) {
int c = id - 'A';
if (cur->child[c] == NULL) cur->child[c] = new tNode();
cur = cur->child[c];
cur->vec.pb(idx);
}
}
void dfs (tNode *cur) {
rep (i, 0, 25) {
if (cur->child[i] != NULL) {
sort (ALL(cur->child[i]->vec));
dfs(cur->child[i]);
}
}
}
pii getRange (tNode *cur, string &S) {
iter (&id, S) {
int c = id - 'A';
if (cur->child[c] == NULL) {
return MP(INF, 0);
}
cur = cur->child[c];
}
return MP(cur->vec[0], cur->vec.back());
}
int get (tNode *cur, string S, pii Range) {
if (Range.fs > Range.se) return 0;
iter (&id, S) {
int c = id - 'A';
if (cur->child[c] == NULL)
return 0;
cur = cur->child[c];
}
// cout << S <<" "<<Range.fs<<" "<<Range.se<<"\n";
int L = lower_bound(ALL(cur->vec), Range.fs) - cur->vec.begin();
int R = upper_bound(ALL(cur->vec), Range.se) - cur->vec.begin();
return R - L;
}
void solution () {
cin >> n >> Q;
vec.resize(n + 1, "");
rep (i, 1, n) {
cin >> vec[i];
}
sort (vec.begin() + 1, vec.end());
rep (i, 1, n) {
Add(proot, vec[i], i);
Add(sroot, Rev(vec[i]), i);
}
dfs(proot);
dfs(sroot);
rep (i, 1, Q) {
string T, Y;
cin >> T >> Y;
cout << get(sroot, Rev(Y), getRange(proot, T)) <<"\n";
}
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +10
5 5
01101
10001
00110
10101
00100
*/
