#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int BlockSize = 317;
const int MaxTrie = 2e6 + 5;
struct Que
{
int l, r, id;
Que() = default;
Que(int _l, int _r, int _id)
{
l = _l;
r = _r;
id = _id;
}
};
int n, m;
string arr[MaxN];
string pre[MaxN];
string suf[MaxN];
void Inp()
{
cin >> n >> m;
for (int x = 1; x <= n; x++)
{
cin >> arr[x];
}
for (int x = 1; x <= m; x++)
{
cin >> pre[x] >> suf[x];
}
sort(arr + 1, arr + n + 1);
}
struct Node
{
int child[4];
int exist, cnt, l, r;
vector<int> contain;
Node()
{
child[0] = child[1] = child[2] = child[3] = -1;
exist = cnt = 0;
l = n + 1;
r = 0;
contain.clear();
}
};
int curPos;
Node Trie[MaxTrie];
int res[MaxN];
int Cov(char a)
{
if (a == 'C')
{
return 0;
}
if (a == 'U')
{
return 1;
}
if (a == 'G')
{
return 2;
}
return 3;
}
void Add(string s, int p)
{
int pos = 0;
for (char x : s)
{
int c = Cov(x);
if (Trie[pos].child[c] == -1)
{
curPos++;
Trie[curPos] = Node();
Trie[pos].child[c] = curPos;
}
pos = Trie[pos].child[c];
Trie[pos].l = min(Trie[pos].l, p);
Trie[pos].r = max(Trie[pos].r, p);
Trie[pos].contain.push_back(p);
Trie[pos].cnt++;
}
Trie[pos].exist++;
}
pair<int, int> GetPlace(string s)
{
int pos = 0;
for (char x : s)
{
int c = Cov(x);
if (Trie[pos].child[c] == -1)
{
return make_pair(-1, -1);
}
pos = Trie[pos].child[c];
}
return make_pair(Trie[pos].l, Trie[pos].r);
}
int BSearch(int pos, int k)
{
int l = 0, r = (int)Trie[pos].contain.size() - 1, mid, res = -1;
while (l <= r)
{
mid = (l + r) / 2;
if (Trie[pos].contain[mid] <= k)
{
res = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return res + 1;
}
int Count(string s, int l, int r)
{
int pos = 0;
for (char x : s)
{
int c = Cov(x);
if (Trie[pos].child[c] == -1)
{
return 0;
}
pos = Trie[pos].child[c];
}
return BSearch(pos, r) - BSearch(pos, l - 1);
}
vector<Que> query;
void Exc()
{
curPos = 0;
Trie[0] = Node();
Trie[0].l = 1;
Trie[0].r = n;
for (int x = 1; x <= n; x++)
{
Add(arr[x], x);
}
for (int x = 1; x <= m; x++)
{
pair<int, int> p = GetPlace(pre[x]);
if (p.first != -1)
{
query.push_back(Que(p.first, p.second, x));
}
else
{
res[x] = 0;
}
//cout << pre[x] << " " << p.first << " " << p.second << "\n";
}
curPos = 0;
Trie[0] = Node();
for (int x = 1; x <= n; x++)
{
reverse(arr[x].begin(), arr[x].end());
//cout << arr[x] << " ";
Add(arr[x], x);
}
for (Que& x : query)
{
reverse(suf[x.id].begin(), suf[x.id].end());
//cout << suf[x.id] << " ";
res[x.id] = Count(suf[x.id], x.l, x.r);
}
for (int x = 1; x <= m; x++)
{
cout << res[x] << "\n";
}
}
int main()
{
//freopen("D.INP", "r", stdin);
//freopen("D.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int w = 1; w <= test; w++)
{
Inp();
Exc();
}
return 0;
}
