#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long
const int mxN = 1e5;
unordered_map<char,ll> mp;
vector<ll> emp;
struct Node
{
vector<ll> end_pos;
Node* children[4];
bool end;
Node(){
end=0;
for(ll i=0;i<4;++i) children[i]=NULL;
}
};
struct Trie{
Node* root = new Node();
void add(string str){
Node* curr = root;
for(auto it:str){
if(curr->children[mp[it]]==NULL) curr->children[mp[it]]=new Node();
curr=curr->children[mp[it]];
}
curr->end=1;
}
void update_pos(string str,bool from_beg,ll idx){
Node* curr=root;
if(!from_beg){
for(int i=str.size()-1;i>=0;--i){
char it=str[i];
if(curr->children[mp[it]]==NULL) return;
curr=curr->children[mp[it]];
if(curr->end){
curr->end_pos.pb(idx);
}
}
return;
}
for(auto it:str){
if(curr->children[mp[it]]==NULL) return;
curr=curr->children[mp[it]];
if(curr->end){
curr->end_pos.pb(idx);
}
}
}
vector<ll> qry(string str){
Node* curr = root;
for(auto it:str){
curr=curr->children[mp[it]];
}
return curr->end_pos;
}
};
void solve(){
mp['A']=0;
mp['C']=1;
mp['G']=2;
mp['U']=3;
Trie pre,suf;
ll n,m;cin>>n>>m;
vector<string> vec(n);
vector<pair<string,string>> pr(m);
for(ll i=0;i<n;++i){
cin>>vec[i];
}
for(ll i=0;i<m;++i){
cin>>pr[i].first>>pr[i].second;
pre.add(pr[i].first);
reverse(all(pr[i].second));
suf.add(pr[i].second);
}
ll idx=0;
for(auto it:vec){
pre.update_pos(it,1,idx);
suf.update_pos(it,0,idx);
++idx;
}
for(auto it:pr){
vector<ll> c1=pre.qry(it.first);
vector<ll> c2=suf.qry(it.second);
if(c1.size()>c2.size()) swap(c1,c2);
ll ans=0,nwst=0;
if(c1.size()==0||c2.size()==0){
cout<<ans<<'\n';
continue;
}
for(auto it:c1){
ll st=nwst,en=c2.size()-1;
while(st<=en){
ll mid=(st+en)/2;
if(c2[mid]==it){
++ans;
nwst=mid+1;
break;
}
if(c2[mid]>it) en=mid-1;
else st=mid+1;
}
}
cout<<ans<<'\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
