#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>
using namespace std;
const int maxn = 1e5 + 2;
string a[maxn];
int idx[300];
struct node1 {
vector<int> t;
node1 *chr[4];
node1() {
for (int i = 0; i < 4;i++) {
chr[i] = nullptr;
}
}
};
struct node2 {
int tmax=0,tmin=1e9;
node2 *chr[4];
node2() : tmax(0), tmin((int)1e9) {
for (int i = 0; i < 4;i++) {
chr[i] = nullptr;
}
}
};
struct trie1 {
node2 *root = new node2();
void update(node2 *p, string &s, int pos, int id) {
p->tmin = min(p->tmin, id);
p->tmax = max(p->tmax, id);
if (pos == s.size()) return;
if (p->chr[idx[s[pos]]] == nullptr) {
p->chr[idx[s[pos]]] = new node2();
}
update(p->chr[idx[s[pos]]],s,pos+1,id);
}
pii get(node2 *p, string &s, int pos) {
if (p==nullptr) return {-1,-1};
if (pos==s.size()) return {p->tmin,p->tmax};
return get(p->chr[idx[s[pos]]], s, pos+1);
}
pii get(string &s) {
return get(root,s,0);
}
void update(string &s, int id) {
update(root,s,0,id);
}
};
struct trie2 {
node1 *root = new node1();
void update(node1 *p, string &s, int pos, int id) {
(p->t).push_back(id);
if (pos == -1) return;
if (p->chr[idx[s[pos]]] == nullptr) {
p->chr[idx[s[pos]]] = new node1();
}
update(p->chr[idx[s[pos]]],s,pos-1,id);
}
void sortnode(node1 *p) {
sort(p->t.begin(),p->t.end());
for (int i = 0; i < 4; i++) {
if (p->chr[i] != nullptr) {
sortnode(p->chr[i]);
}
}
}
int get(node1 *p, string &s, int pos, int mn, int mx) {
// cerr << "get: "<< pos << " " << s[pos] << '\n';
if (p==nullptr) return 0;
if (pos==-1) {
int l = lower_bound(p->t.begin(),p->t.end(),mn) - p->t.begin();
int r = upper_bound(p->t.begin(),p->t.end(),mx) - p->t.begin();
// cerr << "::: "; for (int v : p->t) cerr << v << " "; cerr << '\n';
return r-l;
}
return get(p->chr[idx[s[pos]]],s,pos-1,mn,mx);
}
int get(string &s, int mn, int mx) {
return get(root,s,s.size()-1,mn,mx);
}
void update(string &s, int id) {
update(root,s,s.size()-1,id);
}
};
trie1 pre;
trie2 suf;
void solve() {
idx['A'] = 0;
idx['C'] = 1;
idx['G'] = 2;
idx['U'] = 3;
int n,m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
// cerr << "add:" << a[i] << endl;
pre.update(a[i],i);
suf.update(a[i],i);
}
suf.sortnode(suf.root);
for (int i = 1; i <= m; i++) {
string p,s; cin >> p >> s;
pii pos = pre.get(p);
// cerr << ": " << pos.first << " " << pos.second << '\n';
cout << suf.get(s,pos.first,pos.second) << '\n';
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
return 0;
}
