#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 2e5 + 2;
const int M = 19;
const ll MOD = 1e9 + 7;
const ll INF = 2e9;
const ll base = 311;
const ll base2 = 1e4 + 7;
const int BLOCK_SIZE = 400;
int n, m;
int cur = -1, cur2 = -1;
int cid[200];
void maximize(int &a, int b) {
if (a < b) a = b;
}
void minimize(int &a, int b) {
if (a > b) a = b;
}
struct Trie {
struct node {
int l, r, child[4];
}; vector <node> a;
int new_node() {
node tmp;
memset(tmp.child, -1, sizeof tmp.child);
tmp.l = INF, tmp.r = -INF;
a.push_back(tmp);
return ++cur;
}
void add_node(string s, int id) {
int pos = 0, n = s.size();
for (int i = 0; i < n; i ++) {
int j = cid[s[i]];
if (a[pos].child[j] < 0) {
int tmp = new_node();
a[pos].child[j] = tmp;
}
pos = a[pos].child[j];
minimize(a[pos].l, id);
maximize(a[pos].r, id);
}
}
ii getrange(string s) {
int pos = 0, n = s.size();
for (int i = 0; i < n; i ++) {
int j = cid[s[i]];
if (a[pos].child[j] < 0) return {-1, -1};
pos = a[pos].child[j];
}
return {a[pos].l, a[pos].r};
}
} trie;
struct ReTrie {
struct node {
int child[4];
vector <int> idx;
}; vector <node> a;
int new_node() {
node tmp;
memset(tmp.child, -1, sizeof tmp.child);
tmp.idx.clear();
a.push_back(tmp);
return ++cur2;
}
void add_node(string s, int id) {
reverse(all(s));
int pos = 0, n = s.size();
for (int i = 0; i < n; i ++) {
int j = cid[s[i]];
if (a[pos].child[j] < 0) {
int tmp = new_node();
a[pos].child[j] = tmp;
}
pos = a[pos].child[j];
a[pos].idx.push_back(id);
}
}
int getans(string s, int l, int r) {
reverse(all(s));
int pos = 0, n = s.size();
for (int i = 0; i < n; i ++) {
int j = cid[s[i]];
if (a[pos].child[j] < 0) return 0;
pos = a[pos].child[j];
}
int i = lower_bound(all(a[pos].idx), l) - a[pos].idx.begin();
int j = upper_bound(all(a[pos].idx), r) - a[pos].idx.begin();
return j - i;
}
} trie2;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cid['A'] = 0, cid['G'] = 1, cid['C'] = 2, cid['U'] = 3;
cin >> n >> m;
vector <string> a(n);
for (int i = 0; i < n; i ++) cin >> a[i];
sort(all(a));
trie.new_node();
trie2.new_node();
for (int i = 0; i < n; i ++) {
trie.add_node(a[i], i);
trie2.add_node(a[i], i);
}
while (m --) {
string p, s;
cin >> p >> s;
ii range = trie.getrange(p);
cout << trie2.getans(s, range.fi, range.se) << '\n';
}
}
/*
/\_/\ zzZ
(= -_-)
/ >u >u
*/
