#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef struct item1 * pitem1;
typedef struct item2 * pitem2;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item2 {
pitem2 nxt[4]={nullptr, nullptr, nullptr, nullptr};
int ile=0;
};
struct item1 {
pitem1 nxt[4]={nullptr, nullptr, nullptr, nullptr};
vector<int>pyt;
pitem2 tr=nullptr;
};
vector<int>koduj(string s) {
vector<int>P;
for(auto i : s) {
if(i=='A') P.pb(0);
else if(i=='G') P.pb(1);
else if(i=='C') P.pb(2);
else P.pb(3);
}
return P;
}
const int LIM=1e5+7;
vector<int>V[LIM];
int wynik[LIM];
void dodaj2(pitem2 v, vector<int>&P, int x) {
v->ile+=1;
if(x==0) return;
if(v->nxt[P[x-1]]==nullptr) v->nxt[P[x-1]]=new item2();
dodaj2(v->nxt[P[x-1]], P, x-1);
}
void dodaj(pitem1 v, vector<int>&P, int x) {
if(x==P.size()) {
if(v->tr==nullptr) v->tr=new item2();
dodaj2(v->tr, P, P.size());
return;
}
if(v->nxt[P[x]]==nullptr) v->nxt[P[x]]=new item1();
dodaj(v->nxt[P[x]], P, x+1);
}
void dodaj_pyt(pitem1 v, vector<int>&P, int x, int ind) {
if(x==P.size()) {
v->pyt.pb(ind);
return;
}
if(v->nxt[P[x]]==nullptr) return;
dodaj_pyt(v->nxt[P[x]], P, x+1, ind);
}
void lacz(pitem2 a, pitem2 b) {
a->ile+=b->ile;
rep(i, 4) if(b->nxt[i]!=nullptr) {
if(a->nxt[i]==nullptr) a->nxt[i]=new item2();
lacz(a->nxt[i], b->nxt[i]);
}
}
pitem2 merguj(pitem2 a, pitem2 b) {
if(a==nullptr) return b;
if(b==nullptr) return a;
if(a->ile<b->ile) swap(a, b);
lacz(a, b);
return a;
}
int zejdz(pitem2 v, vector<int>&P, int x) {
if(x==P.size()) return v->ile;
if(v->nxt[P[x]]==nullptr) return 0;
return zejdz(v->nxt[P[x]], P, x+1);
}
void solve(pitem1 v) {
rep(i, 4) if(v->nxt[i]!=nullptr) {
solve(v->nxt[i]);
v->tr=merguj(v->tr, v->nxt[i]->tr);
}
for(auto i : v->pyt) {
wynik[i]=zejdz(v->tr, V[i], 0);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
pitem1 root=new item1();
int n, m;
cin >> n >> m;
rep(i, n) {
string s;
cin >> s;
vector<int>P=koduj(s);
dodaj(root, P, 0);
}
rep(i, m) {
string a, b;
cin >> a >> b;
vector<int>P=koduj(a);
V[i]=koduj(b);
reverse(all(V[i]));
dodaj_pyt(root, P, 0, i);
}
solve(root);
rep(i, m) cout << wynik[i] << '\n';
}
