#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
struct Node
{
vector<Node *> link;
vector<int> fin;
vector<int> qrId;
int cnt = 0;
int cntNodes = 0;
Node()
{
link.resize(5, NULL);
}
};
void add(Node *rt, string s, bool f, int id)
{
auto v = rt;
v->cnt++;
for (char c : s)
{
if (v->link[c - 'a'] == NULL)
{
v->link[c - 'a'] = new Node();
rt->cntNodes++;
}
v = v->link[c - 'a'];
v->cnt++;
}
if (f)
{
reverse(all(s));
v->fin.pb(id);
}
}
void addQ(Node *rt, string s, int id)
{
auto *v = rt;
for (char c : s)
{
if (v != NULL)
v = v->link[c - 'a'];
}
if (v != NULL)
v->qrId.pb(id);
}
int getAns(Node *v, string s)
{
for (char c : s)
{
if (v != NULL)
v = v->link[c - 'a'];
}
return v == NULL ? 0 : v->cnt;
}
int merge(Node *&v, Node *rt)
{
if (!rt)
return 0;
int cntCreated = 0;
if (!v)
{
v = new Node();
cntCreated++;
}
v->cnt += rt->cnt;
for (int i = 0; i < 5; ++i)
cntCreated += merge(v->link[i], rt->link[i]);
delete (rt);
return cntCreated;
}
Node *traverse(Node *v, vector<int> &ans, vector<string> &Qends, vector<string> &strs)
{
if (v == NULL)
return NULL;
Node *curRt = new Node();
for (auto s : v->fin)
add(curRt, strs[s], 0, -1);
for (int i = 0; i < 5; ++i)
{
auto to = traverse(v->link[i], ans, Qends, strs);
if (to)
{
if (to->cntNodes > curRt->cntNodes)
swap(curRt, to);
int added = merge(curRt, to);
assert(added <= min(curRt->cntNodes, to->cntNodes));
curRt->cntNodes += added;
}
}
for (int curId : v->qrId)
{
ans[curId] = getAns(curRt, Qends[curId]);
}
return curRt;
}
struct test
{
map<char, char> letter;
void solve()
{
int n, q;
cin >> n >> q;
letter['A'] = 'a';
letter['G'] = 'b';
letter['C'] = 'c';
letter['U'] = 'd';
auto transform = [&](string &s)
{
for (auto &c : s)
c = letter[c];
};
Node *root = new Node();
vector<string> ends, strs;
for (int i = 0; i < n; ++i)
{
string s;
cin >> s;
transform(s);
add(root, s, 1, i);
reverse(all(s));
strs.pb(s);
}
for (int i = 0; i < q; ++i)
{
string st, en;
cin >> st >> en;
transform(st);
transform(en);
reverse(all(en));
addQ(root, st, i);
ends.pb(en);
}
vector<int> ans(q);
traverse(root, ans, ends, strs);
for (auto el : ans)
cout << el << "\n";
}
};
main()
{
test t;
t.solve();
}
