#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MX = 100005;
int n, q;
int ans[MX];
string a[MX];
tuple<string, string, int> queries[MX];
void nhap(){
cin >> n >> q;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=q; i++){
string p, q;
cin >> p >> q;
queries[i] = {p, q, i};
}
}
int cv(char c){
return c=='A'? 0 : c=='G'? 1 : c=='C'? 2 : c=='U'? 3 : -1;
}
struct Node{
vector<int> id;
Node *child[4];
Node(){
this->id.clear();
for(int t=4; t--;) this->child[t] = NULL;
}
};
Node *root = new Node();
void add(string s, int id){
reverse(s.begin(), s.end());
Node *cur = root;
for(char c: s){
int t = cv(c);
if(cur->child[t] == NULL) cur->child[t] = new Node();
cur = cur->child[t];
cur->id.push_back(id);
}
}
void solve(){
sort(a+1, a+1+n);
sort(queries+1, queries+1+q);
for(int i=1; i<=n; i++) add(a[i], i);
a[0] = "";
a[n+1] = "~";
for(int i=1; i<=q; i++){
string pf, sf; int id;
tie(pf, sf, id) = queries[i];
reverse(sf.begin(), sf.end());
Node *cur = root;
for(char c: sf){
int t = cv(c);
if(cur->child[t] == NULL){
ans[id] = -1;
break;
}
cur = cur->child[t];
}
#define all(x) (x).begin(),(x).end()
if(ans[id] == -1) ans[id] = 0;
else {
int fx = cur->id.size();
for(int lo=0, hi=(int)cur->id.size() - 1; lo<=hi;){
int mid = (lo+hi)>>1;
int p = cur->id[mid];
if(a[p] >= pf) fx = mid, hi = mid - 1;
else lo = mid + 1;
}
int fy = cur->id.size();
for(int lo=0, hi=(int)cur->id.size() - 1; lo<=hi;){
int mid = (lo+hi)>>1;
int p = cur->id[mid];
if(a[p] > pf+"}") fy = mid , hi = mid - 1;
else lo = mid + 1;
}
ans[id] = fy - fx;
}
}
for(int i=1; i<=q; i++) cout << ans[i] << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
nhap();
solve();
return 0;
}
