#include <bits/stdc++.h>
using namespace std;
long long a[2000005][5], b[2000005][5], l[2000005][5], r[2000005][5], id1=1, id2=1;
vector<long long> ans[2000005][5];
string s[100005], pre, suf;
string fix(string s)
{
long long n=s.size(), i;
string t="";
for (i=0; i<n; i++)
{
if (s[i]=='C') {t+='a';}
else if (s[i]=='U') {t+='b';}
else if (s[i]=='G') {t+='c';}
else {t+='d';};
};
return t;
}
void add(string s, long long k)
{
long long n=s.size(), i, j=0;
for (i=0; i<n; i++)
{
if (a[j][s[i]-'a']==0) {a[j][s[i]-'a']=id1++; l[j][s[i]-'a']=r[j][s[i]-'a']=k;}
else {r[j][s[i]-'a']=k;};
j=a[j][s[i]-'a'];
};
}
void addsuf(string s, long long k)
{
long long n=s.size(), i, j=0;
for (i=0; i<n; i++)
{
if (b[j][s[i]-'a']==0) {b[j][s[i]-'a']=id2++;};
ans[j][s[i]-'a'].push_back(k);
j=b[j][s[i]-'a'];
};
}
pair<long long, long long> solvepre(string s)
{
long long n=s.size(), i, j=0;
for (i=0; i<n-1; i++)
{
if (a[j][s[i]-'a']==0) {return {0LL, 0LL};};
j=a[j][s[i]-'a'];
};
return {l[j][s[n-1]-'a'], r[j][s[n-1]-'a']};
}
vector<long long> solvesuf(string s)
{
long long n=s.size(), i, j=0;
vector<long long> v;
for (i=0; i<n-1; i++)
{
if (b[j][s[i]-'a']==0) {return v;};
j=b[j][s[i]-'a'];
};
return ans[j][s[n-1]-'a'];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m, i;
pair<long long, long long> p;
vector<long long> v;
cin >> n >> m;
for (i=1; i<=n; i++)
{
cin >> s[i];
s[i]=fix(s[i]);
};
sort(s+1, s+n+1);
for (i=1; i<=n; i++)
{
add(s[i], i);
reverse(s[i].begin(), s[i].end());
addsuf(s[i], i);
};
while (m--)
{
cin >> pre >> suf;
pre=fix(pre); suf=fix(suf);
p=solvepre(pre);
reverse(suf.begin(), suf.end());
v=solvesuf(suf);
cout << upper_bound(v.begin(), v.end(), p.second)-lower_bound(v.begin(), v.end(), p.first) << "\n";
};
}
