#include <bits/stdc++.h>
using namespace std;
#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))
#define Int __int128
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;
template <class T1, class T2> bool maximize(T1 &x, T2 y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <class T> void remove_duplicate(vector<T> &ve) {
sort (ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
return rng() % r;
}
const int N = 1e5 + 5;
const int inf = 1e9;
const long long INF = 1e18;
const int base = 311;
const int MOD = 1e9 + 7;
template <const int MOD = int(1e9) + 7>
struct Modular {
int value;
Modular(ll x = 0) {
if (-MOD <= x && x < 2 * MOD) {
value = x;
if (value >= MOD) value -= MOD;
if (value < 0) value += MOD;
}
else {
value = x % MOD;
if (value < 0) value += MOD;
}
}
friend istream& operator >> (istream &is, Modular &x) {
return is >> x.value;
}
friend ostream& operator << (ostream &os, Modular x) {
return os << x.value;
}
void operator = (ll x) {
*this = Modular(x);
}
void operator += (Modular x) {
value += x.value;
if (value >= MOD) value -= MOD;
}
void operator += (ll x) {
*this += Modular(x);
}
Modular operator + (Modular x) {
Modular res = *this; res += x;
return res;
}
Modular operator + (ll x) {
return *this + Modular(x);
};
friend Modular operator + (ll x, Modular y){
return y + x;
}
void operator -= (Modular x) {
value -= x.value;
if (value < 0) value += MOD;
}
void operator -= (ll x) {
*this -= Modular(x);
}
Modular operator - (Modular x) {
Modular res = *this; res -= x;
return res;
}
Modular operator - (ll x) {
return *this - Modular(x);
}
friend Modular operator - (ll x, Modular y) {
return Modular(x) - y;
}
void operator *= (Modular x) {
value = 1ll * value * x.value % MOD;
}
void operator *= (ll x) {
*this *= Modular(x);
}
Modular operator * (Modular x) {
Modular res = *this; res *= x;
return res;
}
Modular operator * (ll x) {
return *this * Modular(x);
}
friend Modular operator * (ll x, Modular y) {
return y * x;
}
void operator /= (Modular x) {
*this *= x.inverse();
}
void operator /= (ll x) {
*this *= Modular(x).inverse();
}
Modular operator / (Modular x) {
Modular res = *this; res /= x;
return res;
}
Modular operator / (ll x) {
return *this / Modular(x);
}
friend Modular operator / (ll x, Modular y) {
return x * y.inverse();
}
Modular binpow(ll n) {
Modular res(1), mul = *this;
while (n > 0) {
if (n & 1) res *= mul;
mul *= mul, n >>= 1;
}
return res;
}
Modular binpow(Modular x) {
return binpow(x.value);
}
Modular inverse() {
return binpow(MOD - 2);
}
bool operator == (Modular x) {
return value == x.value;
}
bool operator != (Modular x) {
return value != x.value;
}
};
using ModInt = Modular<MOD>;
int n, m;
int ans[N];
struct Hash {
string s;
vector<ModInt> hash;
Hash() {}
Hash(const string &S) {
s = S; hash.assign(s.size(), 0);
hash[0] = s[0];
for (int i = 1; i < s.size(); ++i)
hash[i] = hash[i - 1] * base + s[i];
}
int size() {
return s.size();
}
ModInt get(int p) {
if (p >= hash.size()) return MOD;
return hash[p];
}
};
bool isLess(Hash &hashA, Hash &hashB) { // return true if A < B
int differ = min(hashA.size(), hashB.size());
int low = 0, high = differ - 1;
while (low <= high) {
int mid = (low + high) >> 1;
if (hashA.get(mid) != hashB.get(mid)) high = (differ = mid) - 1;
else low = mid + 1;
}
if (differ < hashA.size() && differ < hashB.size())
return hashA.s[differ] < hashB.s[differ];
return differ < hashB.size();
}
pii find(vector<Hash> &hash, Hash &hashP) {
int low = 0, high = n - 1, L = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (isLess(hash[mid], hashP)) low = mid + 1;
else high = (L = mid) - 1;
}
if (L == -1) return make_pair(-1, -1);
// cerr << "L = " << L << '\n';
ModInt allP = hashP.get(hashP.size() - 1);
if (hash[L].get(hashP.size() - 1) != allP) return make_pair(-1, -1);
low = L, high = n - 1; int R = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (hash[mid].get(hashP.size() - 1) == allP)
low = (R = mid) + 1;
else high = mid - 1;
}
assert(R != -1);
return make_pair(L, R);
}
struct Query {
int l, r, id;
Query(int _l = 0, int _r = 0, int _id = 0) {
l = _l, r = _r, id = _id;
}
};
vector<Query> que[N];
struct FenwickTree {
using T = int;
vector<T> bit;
FenwickTree() {}
void resize(int n) {
bit.assign(n + 1, 0);
}
void update(int p, T val) {
++p;
for (; p < int(bit.size()); p += p & -p) bit[p] += val;
}
T get(int p) {
++p; T ans = 0;
for (; p > 0; p -= p & -p) ans += bit[p];
return ans;
}
T get(int l, int r) {
return get(r) - get(l - 1);
}
} fen;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
vector<string> s(n);
for (auto &x : s) cin >> x;
sort (s.begin(), s.end());
vector<pair<string, int>> tmp(n);
for (int i = 0; i < n; ++i) {
tmp[i] = make_pair(s[i], i);
reverse(tmp[i].fi.begin(), tmp[i].fi.end());
}
sort (tmp.begin(), tmp.end());
vector<string> t(n);
for (int i = 0; i < n; ++i) {
t[i] = tmp[i].fi;
}
vector<Hash> hashS(n), hashT(n);
for (int i = 0; i < n; ++i) {
hashS[i] = Hash(s[i]);
hashT[i] = Hash(t[i]);
}
for (int i = 1; i <= m; ++i) {
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
Hash hashP(p), hashQ(q);
auto [l1, r1] = find(hashS, hashP);
auto [l2, r2] = find(hashT, hashQ);
if (l1 == -1 || l2 == -1) {
ans[i] = 0;
continue;
}
que[r2].emplace_back(l1, r1, i);
if (l2 > 0) que[l2 - 1].emplace_back(l1, r1, -i);
// cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
}
fen.resize(n);
for (int r2 = 0; r2 < n; ++r2) {
fen.update(tmp[r2].se, 1);
for (auto [l, r, id] : que[r2]) {
int sign = (id > 0) - (id < 0);
ans[abs(id)] += sign * fen.get(l, r);
}
}
for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
return 0;
}
