// Src : Vux2Code
// Note : none
#include <bits/stdc++.h>
#define pq_rvs pll,vector<pll>,greater<pll>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
struct Edge {ll u, v, w;};
const ll alp = 4;
const vector <ll> emptyVec = {};
int enc (char x) {
if (x == 'A') return 0;
if (x == 'C') return 1;
if (x == 'G') return 2;
if (x == 'U') return 3;
return -1;
}
struct PreTrie {
struct Node {
Node* next [alp];
ll l, r;
Node () {
for (int i = 0; i < alp; i ++) next [i] = NULL;
l = -1; r = -1;
}
};
Node* root;
PreTrie () {
root = new Node ();
}
void add (string x, ll y) {
Node* pos = root;
for (int i = 0; i < x. size (); i ++) {
if (pos -> next [enc (x [i])] == NULL) pos -> next [enc (x [i])] = new Node ();
pos = pos -> next [enc (x [i])];
if (pos -> l == -1) pos -> l = y;
pos -> r = max (pos -> r, y);
}
}
pll fin (string x) {
Node* pos = root;
for (int i = 0; i < x. size (); i ++) {
if (pos -> next [enc (x [i])] == NULL) return {-1, -1};
pos = pos -> next [enc (x [i])];
}
return {pos -> l, pos -> r};
}
};
struct SufTrie {
struct Node {
Node* next [alp];
vector <ll> vec;
Node () {
for (int i = 0; i < alp; i ++) next [i] = NULL;
vec. clear ();
}
};
Node* root;
SufTrie () {
root = new Node ();
}
void add (string x, ll y) {
Node* pos = root;
for (int i = x. size () - 1; i >= 0; i --) {
if (pos -> next [enc (x [i])] == NULL) pos -> next [enc (x [i])] = new Node ();
pos = pos -> next [enc (x [i])];
pos -> vec. push_back (y);
}
}
vector <ll> fin (string x) {
Node* pos = root;
for (int i = x. size () - 1; i >= 0; i --) {
if (pos -> next [enc (x [i])] == NULL) return emptyVec;
pos = pos -> next [enc (x [i])];
}
return pos ->vec;
}
};
const ll maxN = 2e5 + 5, inf64 = 1e18, mod = 1e9 + 7, maxLog = 20;
ll t = 1;
ll n, m;
string s [maxN], p, q;
PreTrie pre;
SufTrie suf;
vector <ll> tmp;
pll tmpLR;
void solve () {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> s [i];
sort (s + 1, s + n + 1);
for (int i = 1; i <= n; i ++) {
pre. add (s [i], i);
suf. add (s [i], i);
}
for (int i = 1; i <= m; i ++) {
cin >> p >> q;
tmpLR = pre. fin (p);
tmp = suf. fin (q);
cout << upper_bound (tmp. begin (), tmp. end (), tmpLR. second) - lower_bound (tmp. begin (), tmp. end (), tmpLR. first) << '\n';
}
}
int main (){
ios::sync_with_stdio (0);
cin. tie (0);
cout. tie (0);
// #define task "chill"
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
//cin >> t;
while (t --) solve ();
return 0;
}
