#include <bits/stdc++.h>
using namespace std;
constexpr int S = 2e6 + 5;
int idx(char c)
{
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
return 3;
}
struct Trie
{
int sz;
vector<int> sf[S];
int Tree[S][5];
void Prep()
{
memset(Tree, -1, sizeof(Tree));
sz = 0;
}
void Insert(string a,int p)
{
int nw = 0;
for(int i = 0;i < a.size(); ++i)
{
int id = idx(a[i]);
if(Tree[nw][id] == -1)
Tree[nw][id] = ++sz;
nw = Tree[nw][id];
sf[nw].push_back(p);
}
}
int Find(string a)
{
int nw = 0;
for(int i = 0;i < a.size(); ++i)
{
int id = idx(a[i]);
if(Tree[nw][id] == -1)
return -1;
nw = Tree[nw][id];
}
return nw;
}
} p, q;
string a[S/10];
int x[S];
string l[S/10], r[S/10];
void RvS()
{
int n, m;
p.Prep();
q.Prep();
cin >> n >> m;
for(int i = 1;i <= n; ++i)
{
cin >> a[i];
p.Insert(a[i], i);
}
for(int i = 1;i <= m; ++i)
{
cin >> l[i] >> r[i];
int id = p.Find(l[i]);
x[i] = id;
}
for(int i = 1;i <= n; ++i)
{
reverse(a[i].begin(), a[i].end());
q.Insert(a[i], i);
}
int ans = 0;
for(int i = 1;i <= m; ++i)
{
reverse(r[i].begin(), r[i].end());
int id = q.Find(r[i]);
if(x[i] == -1 || id == -1)
{
cout << 0 << '\n';
continue;
}
int g = 0;
ans = 0;
for(int t : q.sf[id])
{
while(g < p.sf[x[i]].size() && p.sf[x[i]][g] < t) ++g;
if(g < p.sf[x[i]].size() && p.sf[x[i]][g] == t) ans++;
if(g >= p.sf[x[i]].size()) break;
}
cout << ans << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
RvS();
}
