#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6+5, INF = 4e18+9;
struct Trie{
struct Node{
int child[4];
int cnt = 0, exist = 0;
} nodes[maxn*4];
int cur = 0;
Trie(){
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
}
int new_node(){
cur++;
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
return cur;
}
void add(vector<int> a){
int pos = 0;
for(int c : a){
if(nodes[pos].child[c] == -1){
nodes[pos].child[c] = new_node();
}
pos = nodes[pos].child[c];
nodes[pos].cnt++;
}
nodes[pos].exist++;
}
int find(vector<int> a){
int pos = 0;
for(int c : a){
if(nodes[pos].child[c] == -1){
return -1;
}
pos = nodes[pos].child[c];
}
return pos;
}
vector<int> lt, rt;
int timer;
void dfs(){
auto dfs = [&](auto dfs, int u) -> void{
timer++;
lt[u] = timer;
for(int i = 0; i < 4; i++){
int v = nodes[u].child[i];
if(v == -1) continue;
dfs(dfs, v);
}
rt[u] = timer;
};
lt.resize(cur+1);
rt.resize(cur+1);
timer = 0;
dfs(dfs, 0);
}
};
struct que{
int l, r, id, t;
};
struct point{
int x, y;
};
template <class T>
struct Fenwick {
int n, log;
vector<T> bit;
Fenwick(int n) : n(n), log(32 - __builtin_clz(n + 1)), bit(n + 1, 0) {}
void add(int i, T delta) {
for (; i <= n; i += i & -i) {
bit[i] += delta;
}
}
T sum(int i) {
T res = 0;
for (; i > 0; i -= i & -i) {
res += bit[i];
}
return res;
}
T sum(int l, int r) {
T res = 0;
return sum(r)-sum(l-1);
}
int kth(T k) {
T sum = 0;
int pos = 0;
for (int l = log - 1; l >= 0; l--) {
if (pos + (1 << l) <= n && sum + bit[pos + (1 << l)] <= k) {
pos += 1 << l;
sum += bit[pos];
}
}
return pos;
}
};
void solve(){
int n, m;
cin >> n >> m;
auto conv = [&](char c) -> int{
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
if(c == 'U') return 3;
return -1;
};
Trie T1, T2;
vector<point> a(n+1);
for(int i = 1; i <= n; i++){
string S;
cin >> S;
vector<int> s;
for(char c : S){
s.push_back(conv(c));
}
T1.add(s);
int x = T1.find(s);
reverse(s.begin(), s.end());
T2.add(s);
int y = T2.find(s);
a[i] = {x, y};
}
T1.dfs();
T2.dfs();
for(int i = 1; i <= n; i++){
a[i] = {T1.lt[a[i].x], T2.lt[a[i].y]};
}
int N = n*4;
vector<vector<que>> sweepQ(N+1);
vector<vector<point>> sweepA(N+1);
vector<int> ans(m+1, 0);
for(int i = 1; i <= n; i++){
sweepA[a[i].x].push_back(a[i]);
}
for(int i = 1; i <= m; i++){
string P, Q;
cin >> P >> Q;
vector<int> ap, aq;
for(char c : P){
ap.push_back(conv(c));
}
for(char c : Q){
aq.push_back(conv(c));
}
reverse(aq.begin(), aq.end());
int u1 = T1.find(ap), u2 = T2.find(aq);
if(u1 == -1 || u2 == -1){
ans[i] = 0;
}else{
sweepQ[T1.lt[u1]-1].push_back({T2.lt[u2], T2.rt[u2], i, -1});
sweepQ[T1.rt[u1]].push_back({T2.lt[u2], T2.rt[u2], i, 1});
}
}
Fenwick<int> bit(N+1);
for(int i = 1; i <= N; i++){
for(auto it : sweepA[i]){
bit.add(it.y, 1);
}
for(auto it : sweepQ[i]){
ans[it.id] += (ll)it.t*bit.sum(it.l, it.r);
}
}
for(int i = 1; i <= m; i++){
cout << ans[i] << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
