#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> pii;
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 4e6;
const ll A = 911382323;
const ll B = 972663749;
ll modpow(ll x, ll n){
if(n == 0) return 1%mod;
ll u = modpow(x, n/2);
u = (u * u) % mod;
if(n % 2) u = (u * x) % mod;
return u;
}
ll inverse(ll x){
return modpow(x, mod-2);
}
ll add(ll ans, ll val){
ans = (ans + val) % mod;
return ans;
}
ll mul(ll ans, ll val){
ans = (ans * val) % mod;
return ans;
}
ll sub(ll ans, ll val){
ans = (ans - val) % mod;
if(ans < 0) ans += mod;
return ans;
}
ll _div(ll ans, ll val){
ans = (ans * inverse(val)) % mod;
return ans;
}
ll fakt[mxn];
ll bc(ll n, ll k){
return (fakt[n]*inverse((fakt[k]*fakt[n-k])%mod))%mod;
}
ll sq(ll x){
return x*x;
}
ll rsum(ll a, ll b){
return (b-a+1)*(a+b)/2;
}
void prec(){
fakt[0] = 1;
fr(i, 1, mxn){
fakt[i] = mul(fakt[i-1], i);
}
}
string s[mxn];
int trie[mxn][26];
vector<int> g[mxn];
int TRIESIZE = 1;
void add(int id, string s){
int u = 0;
for(auto ch : s){
if(trie[u][ch-'A'] == -1){
trie[u][ch-'A'] = TRIESIZE;
u = TRIESIZE;
++TRIESIZE;
}
else{
u = trie[u][ch-'A'];
}
}
g[u].pb(id);
}
int pos[mxn];
int sz[mxn];
int temp_pos = 0;
void dfs(int u){
pos[u] = temp_pos;
++temp_pos;
sz[u] = 1;
fr(i, 0, 26){
if(trie[u][i] != -1){
dfs(trie[u][i]);
sz[u] += sz[trie[u][i]];
}
}
}
vector<pair<ll, ll> > comp;
void hash_prefixes(int i, int p){
reverse(s[i].begin(), s[i].end());
ll h = s[i][0];
comp.pb({h, p});
fr(j, 1, (int)s[i].size()){
h = (h * A + s[i][j]) % B;
comp.pb({h, p});
}
}
ll fhash(string suf){
ll h = suf[0];
fr(i, 1, (int)suf.size()){
h = (h * A + suf[i]) % B;
}
return h;
}
ll findx(string pre){
ll u = 0;
for(auto ch : pre){
if(trie[u][ch-'A']==-1)return -1;
u = trie[u][ch-'A'];
}
return u;
}
vector<int> v[mxn];
void solve(){
memset(trie, -1, sizeof(trie));
int n, m;
cin >> n >> m;
fr(i, 0, n){
cin >> s[i];
add(i, s[i]);
}
dfs(0);
fr(i, 0, TRIESIZE){
for(auto u : g[i]){
hash_prefixes(u, pos[i]);
}
}
string pre[m];
string suf[m];
ll cval[m];
fr(i, 0, m){
cin >> pre[i] >> suf[i];
reverse(suf[i].begin(), suf[i].end());
ll temp_hash = fhash(suf[i]);
comp.pb({temp_hash, -(i+1)});
}
sort(all(comp));
ll tval = -1;
ll bef = -1;
for(auto u : comp){
if(u.st != bef){
++tval;
}
if(u.nd < 0){
cval[-(u.nd+1)] = tval;
}
else{
v[tval].pb(u.nd);
}
bef = u.st;
}
fr(i, 0, m){
ll x = findx(pre[i]);
if(x == -1){
cout<< 0 <<endl;
continue;
}
ll target_hash = cval[i];
ll le = pos[x];
ll ri = pos[x] + sz[x];
cout << (lower_bound(all(v[target_hash]), ri) - lower_bound(all(v[target_hash]), le)) << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
