#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>
int convert(char x)
{
if(x == 'A')
{
return 0;
}
else if(x == 'G')
{
return 1;
}
else if(x == 'C')
{
return 2;
}
else if(x == 'U')
{
return 3;
}
assert(false);
}
struct node
{
int nxt[4];
int cnt;
node()
{
for(int i = 0; i < 4; i++)
{
nxt[i] = -1;
}
cnt = 0;
}
};
struct Trie
{
std::vector <node> Tree;
Trie()
{
Tree.resize(1);
}
void Add(std::string &s)
{
int node = 0;
Tree[node].cnt++;
for(auto x : s)
{
int tmp = convert(x);
if(Tree[node].nxt[tmp] == -1)
{
Tree[node].nxt[tmp] = (int)Tree.size();
Tree.emplace_back();
}
node = Tree[node].nxt[tmp];
Tree[node].cnt++;
}
}
int Count(std::string &s)
{
int node = 0;
for(auto x : s)
{
int tmp = convert(x);
if(Tree[node].nxt[tmp] == -1)
{
return 0;
}
node = Tree[node].nxt[tmp];
}
return Tree[node].cnt;
}
};
int timer;
std::vector <int> tin, tout;
std::vector <std::pair <int, int> > Position;
Trie Prefix;
Trie IT[1 << 19 | 5];
int n;
std::string s[100005];
int q;
void DFS(int node)
{
timer++;
tin[node] = timer;
for(int i = 0; i < 4; i++)
{
if(Prefix.Tree[node].nxt[i] != -1)
{
DFS(Prefix.Tree[node].nxt[i]);
}
}
tout[node] = timer;
}
void Cal()
{
tin.resize(Prefix.Tree.size());
tout.resize(Prefix.Tree.size());
DFS(0);
for(int i = 0; i < n; i++)
{
int node = 0;
for(auto x : s[i])
{
node = Prefix.Tree[node].nxt[convert(x)];
}
Position.emplace_back(tin[node], i);
}
std::sort(Position.begin(), Position.end());
}
void Build(int node, int l, int r)
{
for(int i = l; i <= r; i++)
{
IT[node].Add(s[Position[i].second]);
}
if(l != r)
{
int mid = (l + r) >> 1;
Build(node << 1, l, mid);
Build(node << 1 | 1, mid + 1, r);
}
}
int Get(int node, int l, int r, int L, int R, std::string &s)
{
if(L > r or R < l)
{
return 0;
}
if(L <= l and r <= R)
{
return IT[node].Count(s);
}
int mid = (l + r) >> 1;
return Get(node << 1, l, mid, L, R, s) + Get(node << 1 | 1, mid + 1, r, L, R, s);
}
void BuildMergeSortTree()
{
for(int i = 0; i < n; i++)
{
reverse(s[i].begin(), s[i].end());
}
Build(1, 0, n - 1);
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n >> q;
for(int i = 0; i < n; i++)
{
std::cin >> s[i];
Prefix.Add(s[i]);
}
Cal();
BuildMergeSortTree();
while(q--)
{
std::string pre, suf;
std::cin >> pre >> suf;
reverse(suf.begin(), suf.end());
int node = 0;
for(auto x : pre)
{
int tmp = convert(x);
if(Prefix.Tree[node].nxt[tmp] == -1)
{
node = -1;
break;
}
node = Prefix.Tree[node].nxt[tmp];
}
if(node == -1)
{
std::cout << 0 << '\n';
}
else
{
int l = tin[node], r = tout[node];
l = lower_bound(Position.begin(), Position.end(), std::make_pair(l, 0)) - Position.begin();
r = upper_bound(Position.begin(), Position.end(), std::make_pair(r, (int)1e9)) - Position.begin() - 1;
std::cout << Get(1, 0, n - 1, l, r, suf) << '\n';
}
}
}
