/**
* Author : Nguyen Tuan Vu
* Created : 02.12.2022
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
void file(){
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
}
const int N = 1e5 + 5;
int n, nquery;
string s[N];
namespace sub2 {
struct TRIE {
struct node {
node *child[26];
vector <int> S;
node() {
REP(i, 26) child[i] = NULL;
}
} *root;
TRIE() {
root = new node();
}
void add(string &x, int ID) {
node *p = root;
for (auto c : x) {
if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
p = p -> child[c - 'A'];
p -> S.push_back(ID - 1);
}
}
vector <int> get(string &x) {
node *p = root;
for (auto c : x) {
if (p -> child[c - 'A'] == NULL) return vector <int> ();
p = p -> child[c - 'A'];
}
return p -> S;
}
} trie[2];
void solve() {
FOR(i, 1, n) {
trie[0].add(s[i], i);
reverse(ALL(s[i]));
trie[1].add(s[i], i);
}
while (nquery--) {
string PREF, SUFF;
cin >> PREF >> SUFF;
reverse(ALL(SUFF));
vector <int> Pref = trie[0].get(PREF);
vector <int> Suff = trie[1].get(SUFF);
int ans = 0;
int j = -1;
REP(i, Pref.size()) {
while (j < (int) Suff.size() - 1 && Suff[j + 1] < Pref[i]) {
++j;
}
if (j == (int) Suff.size() - 1) break;
if (Suff[j + 1] == Pref[i]) ++ans;
}
cout << ans << '\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
file();
cin >> n >> nquery;
FOR(i, 1, n) cin >> s[i];
sub2::solve();
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
