#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <cassert>
using namespace std;
#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::cprint(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif
using VI = vector<int>;
using II = pair<int,int>;
class BinaryIndexedTree {
int N;
vector<int> tree;
public:
BinaryIndexedTree(int _N) : N(_N), tree(_N+1) {}
int query(int idx) const {
assert(idx <= N);
int res = 0;
for (int i = idx; i > 0; i -= (i & -i))
res += tree[i];
return res;
}
int query(int L, int R) const {
R = min(R, N);
L = max(L, 1);
return L <= R ? query(R) - query(L-1) : 0;
}
void update(int idx, int val = 1) {
for (int i = idx; i <= N; i += (i & -i))
tree[i] += val;
}
};
struct Trie {
struct TrieNode {
int child[4];
TrieNode() {
memset(child, -1, sizeof(child));
}
};
vector<TrieNode> nodes;
static const int root = 0; // root is at index 0
Trie() {
// nodes.reserve(8000000);
nodes.push_back(TrieNode()); // 1st node is root
}
int insert(const string& S) {
int cur = root;
for (char c : S) {
int k = c - '0';
int nxt = nodes[cur].child[k];
if (nxt < 0) {
nxt = nodes.size();
nodes.push_back(TrieNode());
nodes[cur].child[k] = nxt;
}
cur = nxt;
}
return cur;
}
int dfs_time;
VI dfs_start, dfs_end;
void dfs(int cur) {
dfs_start[cur] = ++dfs_time;
for (int k = 0; k < 4; ++k) {
int nxt = nodes[cur].child[k];
if (nxt < 0) continue;
dfs(nxt);
}
dfs_end[cur] = dfs_time;
}
void explore() {
dfs_time = 0;
dfs_start = VI(nodes.size());
dfs_end = VI(nodes.size());
dfs(root);
}
int find(const string& S) {
int cur = root;
for (char c : S) {
int k = c - '0';
int nxt = nodes[cur].child[k];
if (nxt < 0) return -1;
cur = nxt;
}
return cur;
}
};
const string valid_chars = "ACGU";
void transform(string& S) {
for (int i = 0; i < (int) S.size(); ++i)
S[i] = '0' + valid_chars.find( S[i] );
}
struct Rect {
II tl, br;
};
struct Event {
int id, x;
char type;
};
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Trie trie_fwd, trie_rev;
int N, M;
cin >> N >> M;
vector<II> IDs;
for (int i = 0; i < N; ++i) {
string chain;
cin >> chain;
transform(chain);
int idx = trie_fwd.insert(chain);
reverse(chain.begin(), chain.end());
int idy = trie_rev.insert(chain);
IDs.emplace_back(idx, idy);
}
DEBUG(IDs);
trie_fwd.explore();
trie_rev.explore();
vector<II> points;
for (II id : IDs) {
points.emplace_back(
trie_fwd.dfs_start[id.first],
trie_rev.dfs_start[id.second]
);
}
for (int i = 0; i < N; ++i)
DEBUG(i, points[i]);
vector<Rect> rects;
for (int j = 0; j < M; ++j) {
string prefix, suffix;
cin >> prefix >> suffix;
transform(prefix);
transform(suffix);
reverse(suffix.begin(), suffix.end());
int idx = trie_fwd.find(prefix);
int idy = trie_rev.find(suffix);
if (idx < 0 or idy < 0) {
rects.push_back({
II(-1, -1), II(-1, -1)
});
}
else {
rects.push_back({
II(trie_fwd.dfs_start[idx], trie_rev.dfs_start[idy]),
II(trie_fwd.dfs_end[idx], trie_rev.dfs_end[idy])
});
}
}
for (int j = 0; j < M; ++j)
DEBUG(j, rects[j].tl, rects[j].br);
vector<Event> events;
for (int i = 0; i < N; ++i)
events.push_back({ i, points[i].first, 'P' });
for (int j = 0; j < M; ++j) {
if (rects[j].tl.first < 0) continue;
events.push_back({ j, rects[j].tl.first, 'L'});
events.push_back({ j, rects[j].br.first, 'R'});
}
sort(events.begin(), events.end(),
[&] (Event a, Event b) -> bool {
if (a.x != b.x)
return a.x < b.x;
if (a.type != b.type)
return a.type < b.type;
return a.id < b.id;
}
);
vector<int> ans(M);
BinaryIndexedTree bit(trie_rev.dfs_time+1);
for (Event e : events) {
DEBUG(e.id, e.type, e.x);
if (e.type == 'P') {
int y = points[e.id].second;
bit.update(y);
}
else if (e.type == 'L') {
int ty = rects[e.id].tl.second;
int by = rects[e.id].br.second;
ans[e.id] += -bit.query(ty, by);
}
else {
int ty = rects[e.id].tl.second;
int by = rects[e.id].br.second;
ans[e.id] += bit.query(ty, by);
}
}
for (int j = 0; j < M; ++j)
cout << ans[j] << '\n';
return 0;
}
