#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pp pop_back
const int L=1e5+10,alp=4;
int n,m;
int ans[L];
vector<int> A[L],B[L],S[L];
map<char,int> MP;
struct trie{
trie* ch[alp];
int cnt;
trie(){
cnt=0;
fill(ch,ch+alp,nullptr);
}
void spread(int c){
if(ch[c] == nullptr){
ch[c] = new trie();
}
}
void put(vector<int>* x,int ind){
cnt++;
if(ind == -1)
return;
int c = (*x)[ind];
spread(c);
ch[c]->put(x,ind-1);
}
int get(vector<int>* x,int ind){
if(ind == -1)
return cnt;
int c = (*x)[ind];
if(ch[c] == nullptr)
return 0;
return ch[c]->get(x,ind-1);
}
void clear(){
for(int c=0;c<alp;c++){
if(ch[c] != nullptr){
ch[c]->clear();
delete ch[c];
ch[c] = nullptr;
}
}
}
void prr(vector<int>* x){
cout<<"node: ";
for(auto i:(*x)){
cout<<i;
}
cout<<endl;
for(int c=0;c<alp;c++){
if(ch[c] != nullptr){
x->pb(c);
ch[c]->prr(x);
x->pp();
}
}
}
};
struct triem{
trie* t;
triem* ch[alp];
vector<int> Q;
vector<int>* H;
triem(){
H = new vector<int>();
t = new trie();
fill(ch,ch+alp,nullptr);
}
void spread(int c){
if(ch[c] == nullptr){
ch[c] = new triem();
}
}
void put(vector<int>* x,int ind,int i){
if(ind == x->size()){
H->pb(i);
t->put(x,x->size()-1);
return;
}
int c = (*x)[ind];
spread(c);
ch[c]->put(x,ind+1,i);
}
void putq(vector<int>* x,int ind,int i){
if(ind == x->size()){
Q.pb(i);
return;
}
int c = (*x)[ind];
spread(c);
ch[c]->putq(x,ind+1,i);
}
void dfs(){
for(int c=0;c<alp;c++){
if(ch[c] == nullptr)
continue;
ch[c]->dfs();
if(ch[c]->H->size() > H->size()){
swap(ch[c]->H, H);
swap(ch[c]->t, t);
}
for(auto i:*(ch[c]->H)){
H->pb(i);
t->put(&S[i],S[i].size()-1);
}
ch[c]->H->clear();
ch[c]->t->clear();
}
/*
if(Q.size()){
vector<int> x;
t->prr(&x);
}
*/
for(auto i:Q){
ans[i] = t->get(&B[i],B[i].size()-1);
}
}
}T;
int main(){
//ifstream cin ("in.in");
MP['A'] = 0;
MP['U'] = 1;
MP['G'] = 2;
MP['C'] = 3;
cin>>n>>m;
for(int i=1;i<=n;i++){
string inp;
cin>>inp;
for(auto c:inp){
S[i].pb(MP[c]);
}
}
for(int i=1;i<=m;i++){
string inp;
cin>>inp;
for(auto c:inp){
A[i].pb(MP[c]);
}
cin>>inp;
for(auto c:inp){
B[i].pb(MP[c]);
}
}
for(int i=1;i<=n;i++){
T.put(&S[i],0,i);
}
for(int i=1;i<=m;i++){
T.putq(&A[i],0,i);
}
T.dfs();
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
}
