#include <bits/stdc++.h>
using namespace std;
int cantitate = 1 , radacina[2000001];
struct Nod { int aparitii[2] = { } , urmatorul[4] = { }; } arbore_1[5000001];
struct __Nod { int aparitii = 0 , urmatorul[4] = { }; } arbore_2[5000001];
stack < pair <int , int> > stiva;
string sir;
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int lungime , numar_intrebari;
cin >> lungime >> numar_intrebari;
for (int indice = 1 ; indice <= lungime ; indice++)
{
cin >> sir;
int nod = 1;
for (auto& valoare : sir)
{
arbore_1[nod].aparitii[0]++;
const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
if (!arbore_1[nod].urmatorul[__urmatorul])
{ arbore_1[nod].urmatorul[__urmatorul] = ++cantitate; }
nod = arbore_1[nod].urmatorul[__urmatorul];
}
arbore_1[nod].aparitii[0]++;
arbore_1[nod].aparitii[1]++;
}
stiva.push({1 , 0});
sir.resize(100001);
cantitate = 0;
{ int __indice = 0;
while (!stiva.empty())
{
const int nod_actual = stiva.top().first;
while (stiva.top().second < 4)
{
if (arbore_1[nod_actual].urmatorul[stiva.top().second])
{
sir[stiva.size() - 1] = ((stiva.top().second < 2 ? (stiva.top().second == 0 ? 'A' : 'U') : (stiva.top().second == 2 ? 'G' : 'C')));
const int nod_vecin = arbore_1[nod_actual].urmatorul[stiva.top().second++];
for (int indice = 1 ; indice <= arbore_1[nod_vecin].aparitii[1] ; indice++)
{
__indice++;
int nod_1 = radacina[__indice - 1] , nod_2 = (radacina[__indice] = ++cantitate);
for (int indice = (int)stiva.size() - 1 ; indice >= 0 ; indice--)
{
const int __urmatorul = (sir[indice] == 'A' || sir[indice] == 'U' ? (sir[indice] == 'A' ? 0 : 1) : (sir[indice] == 'G' ? 2 : 3));
arbore_2[nod_2] = arbore_2[nod_1];
arbore_2[nod_2].aparitii++;
arbore_2[nod_2].urmatorul[__urmatorul] = ++cantitate;
nod_1 = arbore_2[nod_1].urmatorul[__urmatorul];
nod_2 = arbore_2[nod_2].urmatorul[__urmatorul];
}
arbore_2[nod_2] = arbore_2[nod_1];
arbore_2[nod_2].aparitii++;
}
stiva.push({nod_vecin , 0});
break;
}
stiva.top().second++;
}
if (stiva.top().second == 4)
{ stiva.pop(); }
}
}
while (numar_intrebari--)
{
cin >> sir;
int nod = 1 , anterior = 0;
for (auto& valoare : sir)
{
anterior += arbore_1[nod].aparitii[1];
const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
for (int __indice = 0 ; __indice < __urmatorul ; __indice++)
{ anterior += arbore_1[arbore_1[nod].urmatorul[__indice]].aparitii[0]; }
if (!(nod = arbore_1[nod].urmatorul[__urmatorul]))
{ break; }
}
cin >> sir;
reverse(sir.begin() , sir.end());
int nod_1 = radacina[anterior] , nod_2 = radacina[anterior + arbore_1[nod].aparitii[0]];
for (auto &valoare : sir)
{
const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
nod_1 = arbore_2[nod_1].urmatorul[__urmatorul];
nod_2 = arbore_2[nod_2].urmatorul[__urmatorul];
}
cout << arbore_2[nod_2].aparitii - arbore_2[nod_1].aparitii << '\n';
}
return 0;
}
