#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100, mod = 1e9 + 7, p = 701;
long long int ptp[maxn];
vector <int> h[maxn];
string s[maxn];
int cnt;
void init(string s, int ind)
{
h[ind].push_back(0);
for (int i = 0;i < s.size();i++)
{
h[ind].push_back((h[ind][i] + ptp[i] * s[i] % mod) % mod);
}
return ;
}
bool cmp(int a, int b)
{
int l = 0, r = min(h[a].size(), h[b].size());
while (r - l - 1)
{
int mid = (l + r) / 2;
if (h[a][mid] == h[b][mid])
{
l = mid;
}
else
{
r = mid;
}
}
if (r == min(h[a].size(), h[b].size()))
{
return h[a].size() < h[b].size();
}
return s[a][l] < s[b][l];
}
int a[maxn];
struct Node
{
int L, R, mid;
vector <int> s;
Node *lc, *rc;
Node (int l, int r)
{
L = l, R = r, mid = (L + R) / 2, lc = rc = NULL;
return ;
}
void init()
{
if (R - L == 1)
{
s.push_back(a[L]);
return ;
}
lc = new Node(L, mid);
rc = new Node(mid, R);
lc->init();
rc->init();
int lptr = 0, rptr = 0;
while (lptr != mid - L or rptr != R - mid)
{
if (rptr == R - mid or (lptr != mid - L and lc->s[lptr] < rc->s[rptr]))
{
s.push_back(lc->s[lptr]);
lptr++;
}
else
{
s.push_back(rc->s[rptr]);
rptr++;
}
}
return ;
}
int get(int l, int r, int x, int y)
{
if (l >= r or l < L or r > R or x > y)
{
return 0;
}
if (l == L and R == r)
{
return upper_bound(s.begin(), s.end(), y) - lower_bound(s.begin(), s.end(), x);
}
int ret = 0;
if (l < mid)
{
ret += lc->get(l, min(r, mid), x, y);
}
if (r > mid)
{
ret += rc->get(max(l, mid), r, x, y);
}
return ret;
}
};
struct T
{
int L, R, st, ft;
vector <int> add;
T* ch[21];
T()
{
L = maxn, R = 0, st = ft = 0;
for (int i = 0;i < 21;i++)
{
ch[i] = NULL;
}
return ;
}
void insert(int ptr, int ind, int w)
{
L = min(L, w);
R = max(R, w);
if (ptr == s[ind].size())
{
add.push_back(w);
return ;
}
int g = s[ind][ptr] - 'A';
if (ch[g] == NULL)
{
ch[g] = new T();
}
ch[g]->insert(ptr + 1, ind, w);
return ;
}
pair <int, int> get(int ptr)
{
if (ptr == s[0].size())
{
return {L, R};
}
int g = s[0][ptr] - 'A';
if (ch[g] == NULL)
{
return {maxn, 0};
}
return ch[g]->get(ptr + 1);
}
void dfs()
{
st = cnt + 1;
for (auto o : add)
{
a[++cnt] = o;
}
for (int g = 0;g < 21;g++)
{
if (ch[g])
{
ch[g]->dfs();
}
}
ft = cnt + 1;
return ;
}
pair <int, int> getsf(int ptr, int ind)
{
if (ptr == s[ind].size())
{
return {st, ft};
}
int g = s[ind][ptr] - 'A';
if (ch[g])
{
return ch[g]->getsf(ptr + 1, ind);
}
return {0, 0};
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
T *pre, *suf;
pre = new T();
suf = new T();
ptp[0] = 1;
for (int i = 1;i < maxn;i++)
{
ptp[i] = ptp[i - 1] * p % mod;
}
int n, m;
cin >> n >> m;
vector <int> tmp;
for (int i = 1;i <= n;i++)
{
cin >> s[i];
init(s[i], i);
tmp.push_back(i);
}
sort(tmp.begin(), tmp.end(), cmp);
int it = 0;
for (auto o : tmp)
{
pre->insert(0, o, ++it);
reverse(s[o].begin(), s[o].end());
suf->insert(0, o, it);
reverse(s[o].begin(), s[o].end());
}
suf->dfs();
Node* root = new Node(1, cnt + 1);
root->init();
for (int i = 1;i <= cnt;i++)
{
// cout << a[i] << ' ';
}
//cout << endl;
while (m--)
{
cin >> s[0];
pair <int, int> tmp1 = pre->get(0);
cin >> s[0];
reverse(s[0].begin(), s[0].end());
pair <int, int> tmp2 = suf->getsf(0, 0);
//cout << tmp1.first << ' ' << tmp1.second << endl;
//cout << tmp2.first << ' ' << tmp2.second << endl;
cout << root->get(tmp2.first, tmp2.second, tmp1.first, tmp1.second) << '\n';
}
}
