#include <bits/stdc++.h>
using namespace std;
// clang-format off
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
// clang-format on
const string RNA = "AGCU";
map<char, int> to_val;
map<int, char> to_ch;
const int ALPHA = 4;
struct Trie {
struct Node {
int child[ALPHA];
int count;
int exist;
int l, r;
Node() {
fill(child, child + ALPHA, -1);
count = exist = 0;
l = r = -1;
}
int& operator[](int c) { return child[c]; }
};
vector<Node> nodes;
Trie() { nodes.emplace_back(); }
void add(const string& s, int i) {
int at = 0;
for (char ch : s) {
int c = to_val[ch];
if (nodes[at][c] == -1) {
nodes[at][c] = size(nodes);
nodes.emplace_back();
}
at = nodes[at][c];
nodes[at].count++;
if (nodes[at].l == -1) nodes[at].l = nodes[at].r = i;
else {
chmin(nodes[at].l, i);
chmax(nodes[at].r, i);
}
}
nodes[at].exist++;
}
pii get_range(const string& s) {
int at = 0;
pii res = {-1, -1};
for (char ch : s) {
int c = to_val[ch];
if (nodes[at][c] == -1) return res;
at = nodes[at][c];
}
if (at != -1) res = {nodes[at].l, nodes[at].r};
return res;
}
void dfs(int at, string& c_str, vector<string>& ve) {
for (int i = 0; i < nodes[at].exist; i++) ve.pb(c_str);
for (int i = 0; i < 4; i++) {
if (int to = nodes[at][i]; to != -1) {
c_str.push_back(to_ch[i]);
dfs(to, c_str, ve);
c_str.pop_back();
}
}
}
vector<string> sort_str() {
vector<string> ve;
string c_str = "";
dfs(0, c_str, ve);
return ve;
}
};
struct RTrie {
struct Node {
int child[ALPHA];
int count;
int exist;
vector<int> idx;
Node() {
fill(child, child + ALPHA, -1);
count = exist = 0;
}
int& operator[](int c) { return child[c]; }
};
vector<Node> nodes;
RTrie() { nodes.emplace_back(); }
void add(const string& s, int i) {
int at = 0;
for (char ch : s) {
int c = to_val[ch];
if (nodes[at][c] == -1) {
nodes[at][c] = size(nodes);
nodes.emplace_back();
}
at = nodes[at][c];
nodes[at].count++;
nodes[at].idx.pb(i);
}
nodes[at].exist++;
}
int query(string& s, pii range) {
int at = 0;
int res = 0;
for (char ch : s) {
int c = to_val[ch];
at = nodes[at][c];
if (at == -1) return res;
}
vector ve(all(nodes[at].idx));
int l = lower_bound(all(ve), range.fi) - ve.begin();
int r = upper_bound(all(ve), range.se) - ve.begin();
res = r - l;
return res;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
// 古力娜扎
for (int i = 0; i < 4; i++) to_val[RNA[i]] = i;
for (int i = 0; i < 4; i++) to_ch[i] = RNA[i];
int n, m;
cin >> n >> m;
Trie sort_tr;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
sort_tr.add(s, 0);
}
vector<string> ve = sort_tr.sort_str();
Trie tr;
RTrie r_tr;
for (int i = 0; i < n; i++) tr.add(ve[i], i);
for (int i = 0; i < n; i++) {
reverse(all(ve[i]));
r_tr.add(ve[i], i);
}
for (int i = 0; i < m; i++) {
string pr, su;
cin >> pr >> su;
pii range = tr.get_range(pr);
reverse(all(su));
int res = r_tr.query(su, range);
cout << res << '\n';
}
return 0;
}
