// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'
constexpr ll inf = 1e18, N = 2e6 + 10, mod = 1e9 + 7, A = 30;
void addtrie(string x, int pos);
int n, m, sz, nxt[N][A], nxt2[N][A], ans[N], cnt[N], sz2;
string s[N], t[N][2];
vector<int> ind[N], ind2[N];
inline void get_input() {
cin >>n >>m;
for(int i = 0; i < n; i++) {
cin >>s[i];
addtrie(s[i], i);
}
for(int i = 0; i < m; i++) cin >>t[i][0] >>t[i][1];
}
inline void addtrie(string x, int pos) {
int p = 0;
for(int i = 0; i < Sz(x); i++) {
if(nxt[p][x[i] - 'A']) p = nxt[p][x[i] - 'A'];
else p = nxt[p][x[i] - 'A'] = ++sz;
}
p = 0;
for(int i = Sz(x) - 1; i >= 0; i--) {
if(nxt2[p][x[i] - 'A']) p = nxt2[p][x[i] - 'A'];
else p = nxt2[p][x[i] - 'A'] = ++sz2;
}
}
inline void dojob(int x) {
int p = 0;
for(int i = 0; i < Sz(t[x][0]); i++) {
if(!nxt[p][t[x][0][i] - 'A']) return;
p = nxt[p][t[x][0][i] - 'A'];
}
ind[p].push_back(x);
p = 0;
for(int i = Sz(t[x][1]) - 1; i >= 0; i--) {
if(!nxt2[p][t[x][1][i] - 'A']) return;
p = nxt2[p][t[x][1][i] - 'A'];
}
ind2[p].push_back(x);
}
inline void call(int pos) {
int p = 0;
for(int i = 0; i < Sz(s[pos]); i++) {
p = nxt[p][s[pos][i] - 'A'];
for(auto j : ind[p]) {
cnt[j]++;
}
}
p = 0;
for(int i = Sz(s[pos]) - 1; i >= 0; i--) {
p = nxt2[p][s[pos][i] - 'A'];
for(auto j : ind2[p]) {
cnt[j]++;
if(cnt[j] == 2) ans[j]++;
}
}
p = 0;
for(int i = 0; i < Sz(s[pos]); i++) {
p = nxt[p][s[pos][i] - 'A'];
for(auto j : ind[p]) {
cnt[j]--;
}
}
p = 0;
for(int i = Sz(s[pos]) - 1; i >= 0; i--) {
p = nxt2[p][s[pos][i] - 'A'];
for(auto j : ind2[p]) {
cnt[j]--;
}
}
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
get_input();
for(int i = 0; i < m; i++) {
dojob(i);
}
for(int i = 0; i < n; i++) {
call(i);
}
for(int i = 0; i < m; i++) {
cout<<ans[i] <<endl;
}
return 0;
}
