#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef pair<int, int> pii;
const int NMAX = 1e5;
const int LMAX = 2e6;
int N, M, I;
int sol[NMAX + 5];
pii itvy[NMAX + 5];
vector<int> pos[NMAX + 5];
vector<int> upd[LMAX + 5], qry[LMAX + 5];
int getid(char ch)
{
if(ch == 'A') return 0;
if(ch == 'G') return 1;
if(ch == 'C') return 2;
if(ch == 'U') return 3;
return -1;
}
class Trie
{
public:
Trie *nxt[4];
int itv[2];
vector<int> who;
Trie() { nxt[0] = nxt[1] = nxt[2] = nxt[3] = 0; itv[0] = itv[1] = 0; }
};
Trie *root[2];
void insert(Trie *T, string s, int id)
{
for(auto ch: s)
{
int x = getid(ch);
if(T->nxt[x] == 0) T->nxt[x] = new Trie();
T = T->nxt[x];
}
T->who.push_back(id);
}
void DFS(Trie *T)
{
T->itv[0] = ++I;
for(int i = 0; i < 4; i++)
if(T->nxt[i])
DFS(T->nxt[i]);
T->itv[1] = I;
for(auto x: T->who)
pos[x].push_back(T->itv[0]);
}
pii query(Trie *T, string s)
{
for(auto ch: s)
{
int x = getid(ch);
if(T->nxt[x] == 0) return {-1, -1};
T = T->nxt[x];
}
return {T->itv[0], T->itv[1]};
}
class BinaryIndexedTree
{
public:
int N;
vector<int> aib;
void init(int N)
{
aib.resize(N + 5);
}
void U(int pos, int val)
{
for(; pos < aib.size(); pos += (pos & (-pos)))
aib[pos] += val;
}
int Q(int pos)
{
int ans = 0;
for(; pos > 0; pos -= (pos & (-pos)))
ans += aib[pos];
return ans;
}
}aib;
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
cin >> N >> M;
root[0] = new Trie();
root[1] = new Trie();
for(int i = 1; i <= N; i++)
{
string s;
cin >> s;
insert(root[0], s, i);
reverse(s.begin(), s.end());
insert(root[1], s, i);
}
I = 0;
DFS(root[0]);
I = 0;
DFS(root[1]);
for(int i = 1; i <= N; i++)
upd[ pos[i][0] ].push_back(pos[i][1]);
for(int i = 1; i <= M; i++)
{
string pfx, sfx;
cin >> pfx >> sfx;
pii x = query(root[0], pfx);
reverse(sfx.begin(), sfx.end());
pii y = query(root[1], sfx);
if(x.first != -1 && y.first != -1)
{
qry[x.first - 1].push_back(-i);
qry[x.second].push_back(i);
itvy[i] = y;
}
}
aib.init(LMAX);
for(int i = 1; i <= LMAX; i++)
{
for(auto x: upd[i])
aib.U(x, 1);
for(auto id: qry[i])
{
int smn = 1;
if(id < 0) id = -id, smn = -1;
int val = aib.Q(itvy[id].second) - aib.Q(itvy[id].first - 1);
sol[id] += smn * val;
}
}
for(int i = 1; i <= M; i++)
printf("%d\n", sol[i]);
return 0;
}
