#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
inline void Convert(string &inp)
{
for (auto &i : inp)
{
if (i == 'A')
{
i = '0';
}
else if (i == 'C')
{
i = '1';
}
else if (i == 'G')
{
i = '2';
}
else
{
i = '3';
}
}
}
struct NODE
{
int child[4], end, min_id, max_id;
vector<int> id;
inline NODE()
{
id.clear();
end = 0;
min_id = 1e9;
max_id = -1e9;
fill_n(child, 4, -1);
}
};
class TRIE
{
private:
vector<NODE> nodes;
vector<string> sorted;
public:
inline void Init()
{
nodes = {NODE()};
}
inline void Add(string inp, int id)
{
int cur_node = 0, cur_key, i = 0;
do
{
cur_key = inp[i] - '0';
if (nodes[cur_node].child[cur_key] == -1)
{
nodes[cur_node].child[cur_key] = nodes.size();
nodes.push_back(NODE());
}
cur_node = nodes[cur_node].child[cur_key];
nodes[cur_node].end += (i == inp.size() - 1);
nodes[cur_node].min_id = min(nodes[cur_node].min_id, id);
nodes[cur_node].max_id = max(nodes[cur_node].max_id, id);
nodes[cur_node].id.push_back(id);
i++;
} while (i < inp.size());
}
inline void DFS(int ind, string cur)
{
for (int i = 0; i < 4; ++i)
{
if (nodes[ind].child[i] != -1)
{
DFS(nodes[ind].child[i], cur + char(i + '0'));
}
}
for (int i = 0; i < nodes[ind].end; ++i)
{
sorted.push_back(cur);
}
}
inline vector<string> GetTrie()
{
sorted.clear();
DFS(0, "");
return sorted;
}
inline pair<int, int> GetRange(string inp)
{
int cur_node = 0, cur_key, i = 0;
do
{
cur_key = inp[i] - '0';
if (nodes[cur_node].child[cur_key] == -1)
{
return {-1, -1};
}
cur_node = nodes[cur_node].child[cur_key];
if (i == inp.size() - 1)
{
return {nodes[cur_node].min_id, nodes[cur_node].max_id};
}
i++;
} while (i < inp.size());
return {-1, -1};
}
inline int GetNum(string inp, pair<int, int> range)
{
int cur_node = 0, cur_key, i = 0;
do
{
cur_key = inp[i] - '0';
if (nodes[cur_node].child[cur_key] == -1)
{
return 0;
}
cur_node = nodes[cur_node].child[cur_key];
if (i == inp.size() - 1)
{
return upper_bound(nodes[cur_node].id.begin(), nodes[cur_node].id.end(), range.second) -
lower_bound(nodes[cur_node].id.begin(), nodes[cur_node].id.end(), range.first);
}
i++;
} while (i < inp.size());
return 0;
}
} trie1, trie2;
int n, m;
vector<string> s;
string p, q;
int main()
{
setup();
cin >> n >> m;
s.resize(n);
trie1.Init();
for (int i = 0; i < n; ++i)
{
cin >> s[i];
Convert(s[i]);
trie1.Add(s[i], i);
}
s = trie1.GetTrie();
trie1.Init();
trie2.Init();
for (int i = 0; i < n; ++i)
{
trie1.Add(s[i], i);
reverse(s[i].begin(), s[i].end());
trie2.Add(s[i], i);
}
while (m--)
{
cin >> p >> q;
Convert(p);
Convert(q);
reverse(q.begin(), q.end());
cout << trie2.GetNum(q, trie1.GetRange(p)) << "\n";
}
return 0;
}
