//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
struct nodel{
nodel *ch[4] = {NULL , NULL , NULL , NULL};
int time[2];
};
struct noder{
noder *ch[4] = {NULL , NULL , NULL , NULL};
vector<int> tms;
};
int n , m;
vector<string> a;
vector<string> ls , rs;
nodel tirel[10000001];
noder tirer[10000001];
int cntl = 0 , cntr = 0;
nodel *ais[100000];
int ch2int(char &e){
if(e == 'A') return 0;
if(e == 'U') return 1;
if(e == 'G') return 2;
return 3;
}
void addTirel(int inx){
nodel *cur = &tirel[0];
for(int i = 0 ; i < (int)a[inx].size() ; i++){
int d = ch2int(a[inx][i]);
if((cur -> ch)[d] == NULL) (cur -> ch)[d] = &tirel[++cntl];
cur = (cur -> ch)[d];
}
ais[inx] = cur;
}
int timer = -1;
void dfsTirel(nodel *cur = &tirel[0]){
(cur -> time)[0] = ++timer;
for(int u = 0 ; u < 4 ; u++) if((cur -> ch)[u] != NULL) dfsTirel((cur -> ch)[u]);
(cur -> time)[1] = timer;
}
void addTirer(int inx){
noder *cur = &tirer[0];
for(int i = (int)a[inx].size() - 1 ; i >= 0 ; i--){
int d = ch2int(a[inx][i]);
if((cur -> ch)[d] == NULL) (cur -> ch)[d] = &tirer[++cntr];
cur = (cur -> ch)[d];
(cur -> tms).pb((ais[inx] -> time)[0]);
}
}
void drawTirer(){
for(int i = 0 ; i <= cntr ; i++) sort((tirer[i].tms).bg() , (tirer[i].tms).end());
}
nodel *getTirel(int inx){
nodel *cur = &tirel[0];
for(int i = 0 ; i < (int)ls[inx].size() ; i++){
int d = ch2int(ls[inx][i]);
if((cur -> ch)[d] == NULL) return NULL;
cur = (cur -> ch)[d];
}
return cur;
}
noder *getTirer(int inx){
noder *cur = &tirer[0];
for(int i = (int)rs[inx].size() - 1 ; i >= 0 ; i--){
int d = ch2int(rs[inx][i]);
if((cur -> ch)[d] == NULL) return NULL;
cur = (cur -> ch)[d];
}
return cur;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0 ; i < n ; i++){
string d;
cin >> d;
a.pb(d);
}
for(int i = 0 ; i < m ; i++){
string l , r;
cin >> l >> r;
ls.pb(l) , rs.pb(r);
}
for(int i = 0 ; i < n ; i++) addTirel(i);
dfsTirel();
for(int i = 0 ; i < n ; i++) addTirer(i);
drawTirer();
for(int i = 0 ; i < m ; i++){
auto itr1 = getTirel(i);
auto itr2 = getTirer(i);
if(itr1 == NULL or itr2 == NULL){
cout << "0\n";
continue;
}
int l = (itr1 -> time)[0] , r = (itr1 -> time)[1];
int o = int(ub((itr2 -> tms).bg() , (itr2 -> tms).end() , r) - lb((itr2 -> tms).bg() , (itr2 -> tms).end() , l));
cout << o << endl;
}
}
