#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
const int mxN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
map<char,ll> id;
struct Node{
Node* children[4];
vector<ll> points;
Node(){
for(ll i=0;i<4;++i) children[i]=NULL;
}
};
Node* p_root=new Node();
Node* s_root=new Node();
void add(Node* curr,string str,ll idx){
for(auto it:str){
if(curr->children[id[it]]==NULL) curr->children[id[it]]=new Node();
curr=curr->children[id[it]];
curr->points.pb(idx);
}
}
pair<ll,ll> qry(Node* curr,string str){
for(auto it:str){
if(curr->children[id[it]]==NULL) return {INF,-INF};
curr=curr->children[id[it]];
}
return {curr->points[0],curr->points[curr->points.size()-1]};
}
string rev(string str){
string ans;
for(ll i=str.size()-1;i>=0;--i){
ans.pb(str[i]);
}
return ans;
}
void solve() {
ll n,m;cin>>n>>m;
vector<string> full_str(n);
for(auto &it:full_str) cin>>it;
sort(all(full_str));
id['A']=0;
id['C']=1;
id['G']=2;
id['U']=3;
ll idx=1;
for(auto it:full_str){
add(p_root,it,idx);
add(s_root,rev(it),idx++);
}
for(ll i=0;i<m;++i){
string l,r;cin>>l>>r;
pair<ll,ll> p_range=qry(p_root,l);
if(p_range.first>p_range.second) cout<<0<<nl;
else{
bool f=0;
Node* curr=s_root;
for(auto it:rev(r)){
if(curr->children[id[it]]==NULL){
cout<<0<<nl;
f=1;
break;
}
curr=curr->children[id[it]];
}
if(!f){
ll l=lower_bound(all(curr->points),p_range.first)-curr->points.begin();
ll r=upper_bound(all(curr->points),p_range.second)-curr->points.begin();
cout<<r-l<<nl;
}
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
