#include <bits/stdc++.h>
using namespace std;
struct Trie
{
struct Node
{
array<int, 4> nxt;
int tin=-1, tout=-1;
Node()
{
fill(nxt.begin(), nxt.end(), -1);
}
};
vector<Node> nodes;
int time=0;
Trie()
{
nodes.emplace_back();
}
int addWord(const vector<int> &word)
{
int curPos = 0;
for (auto car : word)
{
if (nodes[curPos].nxt[car] == -1)
{
nodes[curPos].nxt[car] = nodes.size();
nodes.emplace_back();
}
curPos = nodes[curPos].nxt[car];
}
return curPos;
}
void dfs(int iNoeud)
{
nodes[iNoeud].tin = time++;
for (auto iProchain : nodes[iNoeud].nxt)
if (iProchain != -1)
dfs(iProchain);
nodes[iNoeud].tout= time++;
}
void init()
{
dfs(0);
}
int traverse(const vector<int> &word)
{
int curPos = 0;
for (auto car : word)
{
if (nodes[curPos].nxt[car] == -1)
return -1;
curPos = nodes[curPos].nxt[car];
}
return curPos;
}
};
struct Fenwick
{
vector<int> arr;
int N;
Fenwick(int nbElem)
{
arr.resize(nbElem+1);
N = nbElem+1;
}
void update(int pos, int delta)
{
for (pos++; pos < N; pos += pos&-pos)
arr[pos] += delta;
}
int sum(int r) // sum < r
{
int ret(0);
for (; r; r -= r&-r)
ret += arr[r];
return ret;
}
int sum(int l, int r) // sum[l, r[
{
return sum(r) - sum(l);
}
};
struct Fenwick2d
{
vector<Fenwick> fen;
int lim;
vector<vector<int>> ys;
Fenwick2d(int LIM) : lim(LIM+1), ys(lim) {}
void fakeUpdate(int x, int y)
{
for (++x, ++y; x < lim; x += x&-x)
ys[x].push_back(y);
}
void init()
{
for (int x(0); x < lim; ++x)
{
sort(ys[x].begin(), ys[x].end());
ys[x].resize(unique(ys[x].begin(), ys[x].end())-ys[x].begin());
fen.emplace_back(ys[x].size()+1);
}
}
int getInd(int x, int y)
{
return lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin();
}
void update(int x, int y, int delta)
{
y++;
for (x++; x < lim; x += x & -x)
fen[x].update(getInd(x, y), delta);
}
int sum(int x, int y)
{
int ret=0;
//cout << "query : " << x << ' ' << y << ' ';
y++;
for (; x; x -= x & -x)
ret += fen[x].sum(getInd(x, y));
//cout << ret << endl;
return ret;
}
int sum(int lx, int rx, int ly, int ry)
{
return sum(rx+1, ry+1) - sum(lx, ry+1) - sum(rx+1, ly) + sum(lx, ly);
}
};
const int MAX = 256;
int charDecode[MAX];
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
charDecode[(int)'A'] = 0;
charDecode[(int)'C'] = 1;
charDecode[(int)'G'] = 2;
charDecode[(int)'U'] = 3;
int nbChaines, nbRequetes;
cin >> nbChaines >>nbRequetes;
vector<vector<int>> chaines(nbChaines);
vector<pair<int, int>> posTrie;
Trie chainesEndroit, chainesEnvers;
Fenwick2d fen((int)4e6+10);
for (auto &v : chaines)
{
string s;
cin >> s;
for (auto c : s)
v.push_back(charDecode[(int)c]);
int a = chainesEndroit.addWord(v);
reverse(v.begin(), v.end());
int b = chainesEnvers.addWord(v);
posTrie.emplace_back(a, b);
}
chainesEndroit.init(); chainesEnvers.init();
vector<pair<vector<int>, vector<int>>> requetes(nbRequetes);
for (auto [a, b] : posTrie)
fen.fakeUpdate(chainesEndroit.nodes[a].tin, chainesEnvers.nodes[b].tin);
fen.init();
for (auto [a, b] : posTrie)
{
//cout << chainesEndroit.nodes[a].tin << ' ' << chainesEnvers.nodes[b].tin << endl;
fen.update(chainesEndroit.nodes[a].tin, chainesEnvers.nodes[b].tin, 1);
}
for (auto &[p, q] : requetes)
{
string s, t;
cin >> s >> t;
for (auto v: s)
p.push_back(charDecode[(int)v]);
for (auto v : t)
q.push_back(charDecode[(int)v]);
reverse(q.begin(), q.end());
int posEndroit = chainesEndroit.traverse(p);
int posEnvers = chainesEnvers.traverse(q);
if (posEndroit == -1 or posEnvers == -1)
cout << 0 << '\n';
else
{
int lx(chainesEndroit.nodes[posEndroit].tin);
int rx(chainesEndroit.nodes[posEndroit].tout);
int ly(chainesEnvers.nodes[posEnvers].tin);
int ry(chainesEnvers.nodes[posEnvers].tout);
int ret = fen.sum(lx, rx, ly, ry);
//cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << ' ';
cout << ret << '\n';
}
}
}
