#include <bits/stdc++.h>
using namespace std;
int getNum(char f) {
return f == 'A' ? 0 : f == 'U' ? 1 : f == 'G' ? 2 : 3;
}
struct node {
int child[4][4];
int cnt;
node() : cnt(0) {
memset(child, -1, sizeof(child));
}
};
struct Trie {
vector<node> pool;
int root;
Trie() {
pool.emplace_back();
root = 0;
}
void add(const string &s) {
int u = root;
int n = s.size();
for (int i = 0; i < n; ++i) {
int c1 = getNum(s[i]), c2 = getNum(s[n - i - 1]);
if (pool[u].child[c1][c2] == -1) {
pool[u].child[c1][c2] = pool.size();
pool.emplace_back();
}
u = pool[u].child[c1][c2];
pool[u].cnt++;
}
}
int solve(const string &s, const string &v) {
int u = root;
int n = s.size(), m = v.size();
int len = min(n, m), head = 0, tail = INT_MAX;
string rv = v;
reverse(rv.begin(), rv.end());
for (int i = 0; i < len; ++i) {
int c1 = getNum(s[i]), c2 = getNum(rv[i]);
if (pool[u].child[c1][c2] == -1) return 0;
u = pool[u].child[c1][c2];
}
head = pool[u].cnt;
queue<int> q;
q.push(u);
if (n < m) {
for (int i = n; i < m; ++i) {
int c = getNum(rv[i]);
int sz = q.size();
for (int j = 0; j < sz; ++j) {
int top = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nxt = pool[top].child[k][c];
if (nxt != -1) q.push(nxt);
}
}
}
} else if (n > m) {
for (int i = m; i < n; ++i) {
int c = getNum(s[i]);
int sz = q.size();
for (int j = 0; j < sz; ++j) {
int top = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nxt = pool[top].child[c][k];
if (nxt != -1) q.push(nxt);
}
}
}
} else {
return head;
}
if (q.empty()) return 0;
tail = 0;
while (!q.empty()) {
int top = q.front();
q.pop();
tail += pool[top].cnt;
}
return min(head, tail);
}
};
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
Trie trie;
int n,m;cin>>n>>m;
while(n--) {
string x;cin>>x;
trie.add(x);
}
while(m--) {
string u,v;cin>>u>>v;
cout << trie.solve(u,v)<<'\n';
}
return 0;
}
