#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define DIM 100005
using namespace std;
int n, m, k, i, j, u, ii;
int ind[DIM], sol[DIM];
char p[DIM], q[DIM];
vector<char> v[DIM], c[DIM];
struct str{
int p, u, ind;
};
str w[DIM];
struct trie1{
int minim, maxim;
trie1 *f[5];
trie1(){
minim = 10000000;
maxim = 0;
f[4] = f[1] = f[2] = f[3] = NULL;
}
};
trie1 *r1;
struct trie2{
vector<int> v;
trie2 *f[5];
trie2(){
f[4] = f[1] = f[2] = f[3] = NULL;
}
};
trie2 *r2;
void read(char s[]){
cin>> s;
k = strlen(s);
for(int i = 0; i < k; i++){
if(s[i] == 'A'){
s[i] = 1;
}
if(s[i] == 'C'){
s[i] = 2;
}
if(s[i] == 'G'){
s[i] = 3;
}
if(s[i] == 'U'){
s[i] = 4;
}
}
}
int cmp2(str a, str b){
return a.p > b.p;
}
int cmp(int a, int b){
for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){
if(v[a][i] != v[b][i]){
return v[a][i] < v[b][i];
}
}
return v[a].size() < v[b].size();
}
void adauga1(trie1 *r, char *s, int ind){
r->minim = min(r->minim, ind);
r->maxim = max(r->maxim, ind);
if(*s != 0){
if(r->f[*s] == NULL){
r->f[*s] = new trie1;
}
adauga1(r->f[*s], s + 1, ind);
}
}
void query1(trie1 *r, char *s, str &w){
if(*s == 0){
w.p = r->minim;
w.u = r->maxim;
}
else{
if(r->f[*s] != NULL){
query1(r->f[*s], s + 1, w);
}
}
}
void adauga2(trie2 *r, char *s, int ind){
r->v.push_back(ind);
if(*s != 0){
if(r->f[*s] == NULL){
r->f[*s] = new trie2;
}
adauga2(r->f[*s], s + 1, ind);
}
}
int query2(trie2 *r, char *s, int ind){
if(*s == 0){
int st, dr, mid;
st = 0;
dr = r->v.size() - 1;
while(st <= dr){
mid = (st + dr) / 2;
if(r->v[mid] <= ind){
dr = mid - 1;
}
else{
st = mid + 1;
}
}
return r->v.size() - st;
}
if(r->f[*s] == NULL){
return 0;
}
return query2(r->f[*s], s + 1, ind);
}
void copiere(vector<char> v){
for(int i = 0; i < v.size(); i++){
p[i] = v[i];
}
p[ v.size() ] = 0;
}
int main(){
r1 = new trie1;
r2 = new trie2;
cin>> n >> m;
for(i = 1; i <= n; i++){
read(p);
ind[i] = i;
for(j = 0; j < k; j++){
v[i].push_back(p[j]);
}
}
sort(ind + 1, ind + n + 1, cmp);
for(i = 1; i <= n; i++){
copiere(v[ ind[i] ]);
adauga1(r1, p, i);
}
for(i = 1; i <= m; i++){
read(p);
w[i].ind = i;
w[i].p = 1000000;
query1(r1, p, w[i]);
read(q);
for(j = 0; j < k; j++){
c[i].push_back(q[j]);
}
}
sort(w + 1, w + m + 1, cmp2);
u = 1;
for(ii = 1; ii <= n; ii++){
for(i = 0, j = v[ii].size() - 1; i < j; i++, j--){
swap(v[ii][i], v[ii][j]);
}
}
for(ii = 1; ii <= m; ii++){
for(i = 0, j = c[ii].size() - 1; i < j; i++, j--){
swap(c[ii][i], c[ii][j]);
}
}
while(w[u].p > n){
u++;
}
for(i = n; i >= 1; i--){
copiere(v[ ind[i] ]);
adauga2(r2, p, i);
while(w[u].p == i){
copiere(c[ w[u].ind ]);
sol[ w[u].ind ] = query2(r2, p, w[u].u);
u++;
}
}
for(i = 1; i <= m; i++){
cout<< sol[i] <<"\n";
}
}
