#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define fi first
#define se second
#define fr front
#define pfr push_front
#define pofr pop_front
#define pob pop_back
#define For(a,b,c,d) for(auto a = b;(d > 0&&a <= c) || (d < 0&&a >= c);a+=d)
#define MSK(k) (1ULL<<(k))
#define PROBLEM ""
using namespace std;
const int maxN = 1e5,maxNode = 2e6;;
int n,m;
string str[maxN+7];
struct nodeTrie{
int child[3];
vector<int> index;
nodeTrie(){
memset(child,0,sizeof child);
index.clear();
}
}trie[maxNode+7];
int cntNode;
int findId(char c){
if(c == 'A')
return 0;
if(c == 'G')
return 1;
return 2;
}
void addTrie(string s,int index){
int u = 0;
for(auto c : s){
int id = findId(c);
if(!trie[u].child[id])
trie[u].child[id] = ++cntNode;
u = trie[u].child[id];
trie[u].index.pb(index);
}
return;
}
int cnp(string s){
int l = 1,r = n;
while(l <= r){
int mid = (l+r)>>1;
str[mid] >= s ? r = mid-1 : l = mid+1;
}
return l;
}
vector<int> getIndex(string s){
int u = 0;
for(auto c : s){
int id = findId(c);
if(!trie[u].child[id])
return trie[0].index;
u = trie[u].child[id];
}
return trie[u].index;
}
int main()
{
// freopen(PROBLEM".INP","r",stdin);
// freopen(PROBLEM".OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
For(i,1,n,1)
cin>>str[i];
sort(str+1,str+n+1);
For(i,1,n,1){
reverse(str[i].begin(),str[i].end());
addTrie(str[i],i);
reverse(str[i].begin(),str[i].end());
}
For(i,1,m,1){
string p,q;cin>>p>>q;
int l = cnp(p);
p += 'Z';
int r = cnp(p);
reverse(q.begin(),q.end());
vector<int> index = getIndex(q);
sort(index.begin(),index.end());
int idLow = lower_bound(index.begin(),index.end(),l)-index.begin();
int idUp = lower_bound(index.begin(),index.end(),r)-index.begin();
cout<<idUp-idLow<<"\n";
// cout<<" "<<l<<" "<<r<<"\n";
}
return 0;
}
