#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "test"
using namespace std;
typedef long long ll;
constexpr int S = 1300, maxn = 1e5;
int pfsz[maxn];
map<char, char> M = {{'A', 'A'}, {'G', 'B'}, {'C', 'C'}, {'U', 'D'}};
struct query
{
int l, r, idx, res = 0;
bool operator<(const query &q)
{
if (pfsz[l]/S == pfsz[q.l]/S)
return r < q.r;
return l < q.l;
}
};
struct node
{
node *child[4];
int cnt;
node()
{
for (int i = 0; i < 4; ++i)
child[i] = nullptr;
cnt = 0;
}
} *root = new node();
void add(string &s)
{
node *p = root;
for (char &c: s)
{
if (!p->child[c - 'A'])
p->child[c - 'A'] = new node();
p = p->child[c - 'A'];
p->cnt++;
}
}
bool rmv(node *p, string &s, int i)
{
if (i < s.size() && rmv(p->child[s[i] - 'A'], s, i+1))
p->child[s[i] - 'A'] = nullptr;
p->cnt--;
if (p->cnt == 0)
{
delete p;
return true;
}
return false;
}
void rmv(string &s){rmv(root, s, 0);}
int cntpref(string &s)
{
node *p = root;
for (char &c: s)
{
if (p->child[c - 'A'] == nullptr)
return 0;
p = p->child[c - 'A'];
}
return p->cnt;
}
void solve()
{
int n, m; cin>>n>>m;
vector<string> S(n), X(m), Y(m);
vector<query> Q(m);
for (int i = 0; i < n; ++i)
{
cin>>S[i];
for (char &c: S[i])
c = M[c];
pfsz[i] = (i == 0 ? 0 : pfsz[i-1]) + S[i].size();
}
sort(S.begin(), S.end());
for (int i = 0; i < m; ++i)
{
cin>>X[i]>>Y[i];
for (char &c: X[i])
c = M[c];
for (char &c: Y[i])
c = M[c];
Q[i].l = lower_bound(S.begin(), S.end(), X[i]) - S.begin();
Q[i].r = upper_bound(S.begin(), S.end(), X[i] + 'Z') - S.begin() - 1;
Q[i].idx = i;
}
sort(Q.begin(), Q.end());
for (string &s: S)
reverse(s.begin(), s.end());
for (string &s: Y)
reverse(s.begin(), s.end());
int l = 0, r = -1;
for (query &q: Q)
{
if (q.l > q.r)
continue;
while (l > q.l)
add(S[--l]);
while (r < q.r)
add(S[++r]);
while (l < q.l)
rmv(S[l++]);
while (r > q.r)
rmv(S[r--]);
q.res = cntpref(Y[q.idx]);
}
sort(Q.begin(), Q.end(), [](query &p, query &q){return p.idx < q.idx;});
for (query &q: Q)
cout<<q.res<<"\n";
}
int main()
{
if (fopen(_F".INP", "r"))
{
freopen(_F".INP", "r", stdin);
//freopen(_F".OUT", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
int Test = 1; //cin>>Test;
while (Test--) solve();
}
