//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
typedef pair<string, int> psi;
int n, q;
vector<string> vec;
vector< psi > suf;
vector<string> prefix;
vector<string> suffix;
const int maxlen = 2e6+5;
char tmp[maxlen];
bool cmp(psi a, psi b)
{
reverse(a.X.begin(), a.X.end());
reverse(b.X.begin(), b.X.end());
return a.X< b.X;
}
struct node
{
int v;
node *left, *right;
node(int a, node *b, node *c)
{
v = a;
left = b; right = c;
}
node* insert(int dat, int L = 1, int R = n)
{
if(L<= dat && dat<= R)
{
if(L == R) return new node(v+1, NULL, NULL);
int M = (L+R)/2;
return new node(v+1, left->insert(dat, L, M), right->insert(dat, M+1, R));
}
return this;
}
int ask(int i, int j, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return v;
int M = (L+R)/2;
int x = left->ask(i, j, 2*p, L, M);
int y = right->ask(i, j, 2*p+1, M+1, R);
return x+y;
}
};
node *zero = new node(0, NULL, NULL);
node* root[maxlen];
int match(vector<string> &yo, int ind, string &x)
{
for(int i = 0; i< (int) x.size() && i< (int) yo[ind].size(); i++)
if(yo[ind][i] != x[i]) return i;
return min(x.size(), yo[ind].size());
}
ii findra(vector<string> &yo, string &x)
{
//find first to >=
int lo = 1, hi = n;
int k = x.size();
while(lo< hi)
{
int mid = (lo+hi)/2;
if(yo[mid]> x and match(yo, mid, x) == k) hi = mid;
else if(yo[mid] >= x) hi = mid;
else lo = mid+1;
}
int lend = lo;
// printf("lend is %d for %s\n", lend, x.c_str());
if(match(yo, lend, x) != k) return ii(-1, -1);
lo = 1, hi = n;
//find last to <=
while(lo< hi)
{
int mid = (lo+hi+1)/2;
// printf("match %d is %d\n", mid, match(yo, mid, x));
if(yo[mid]> x and match(yo, mid, x) == k) lo = mid;
else if(yo[mid]> x) hi = mid-1;
else lo = mid;
}
return ii(lend, lo);
}
int main()
{
zero = new node(0, NULL, NULL);
zero->left = zero->right = zero;
scanf("%d %d", &n, &q);
vec.pb("@");
for(int i = 1; i<= n; i++)
{
scanf("%s", tmp);
vec.pb(string(tmp));
}
sort(vec.begin(), vec.end());
for(int i = 1; i<= n; i++)
{
suf.pb(make_pair(vec[i], i));
reverse(suf.back().X.begin(), suf.back().X.end());
}
suf.pb(make_pair("@", 0));
sort(suf.begin(), suf.end());
// for(int i = 1; i<= n; i++) printf("%d: %s\n", i, vec[i].c_str());
// for(int i = 1; i<= n ;i++) printf("%d: %s\n", i, suf[i].X.c_str());
for(int i = 1; i<= n; i++)
{
// printf("%d ", suf[i].Y);
root[i] = (i> 1?root[i-1]:zero)->insert(suf[i].Y);
}
// printf("\n");
swap(prefix, vec);
for(int i = 0; i<= n; i++) suffix.pb(suf[i].X);
while(q--)
{
string prf, sf;
scanf("%s", tmp);
prf = string(tmp);
scanf("%s", tmp);
sf = string(tmp);
reverse(sf.begin(), sf.end());
auto res = findra(prefix, prf);
auto res2 = findra(suffix, sf);
if(res.X == -1 or res2.Y == -1)
{
puts("0");
continue;
}
int x1 = res.X, x2 = res.Y;
int y1 = res2.X, y2 = res2.Y;
// printf("(%d, %d)\n", x1, x2);
// printf("(%d, %d)\n", y1, y2);
int ret = root[y2]->ask(x1, x2)-(y1>1?root[y1-1]->ask(x1, x2):0);
ret = max(ret, 0);
printf("%d\n", ret);
}
}
