#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int st[N], fn[N], timer;
string s[N];
void convert(string &s) {
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == 'A') s[i] = 0;
if (s[i] == 'G') s[i] = 1;
if (s[i] == 'C') s[i] = 2;
if (s[i] == 'U') s[i] = 3;
}
return ;
}
struct Trie {
vector <int*> vec = {new int[5]{}};
inline int* operator [] (int i) {return vec[i];}
inline void add(string s) {
int cur = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (!vec[cur][(int)s[i]]) vec[cur][(int)s[i]] = vec.size(), vec.push_back(new int[5]{});;
cur = vec[cur][(int)s[i]];
vec[cur][4]++;
}
return ;
}
inline int get(string s) {
int cur = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (!vec[cur][(int)s[i]]) return 0;
cur = vec[cur][(int)s[i]];
}
return cur;
}
inline int count(string s) {return vec[get(s)][4];}
} T, seg[N<<2];
void dfs(int v) {
st[v] = timer++;
for (int i = 0; i < 4; i++) if (T[v][i]) dfs(T[v][i]);
fn[v] = timer;
}
void Add(const int &l, const string &s, int L = 0, int R = timer, int id = 1) {
seg[id].add(s);
if (R - L == 1) return ;
int mid = (L+R)>>1;
if (l < mid) Add(l, s, L, mid, id<<1);
else Add(l, s, mid, R, id<<1|1);
return ;
}
int Get(const int &l, const int &r, const string &s, int L = 0, int R = timer, int id = 1) {
if (r <= L || R <= l) return 0;
if (l <= L && R <= r) return seg[id].count(s);
int mid = (L+R)>>1;
return Get(l, r, s, L, mid, id<<1) + Get(l, r, s, mid, R, id<<1|1);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) cin >> s[i], convert(s[i]), T.add(s[i]);
dfs(0);
for (int i = 0; i < n; i++) {
int v = T.get(s[i]);
reverse(s[i].begin(), s[i].end());
Add(st[v], s[i]);
}
for (int i = 0; i < m; i++){
string p, q; cin >> p >> q, convert(p), convert(q);
int v = T.get(p);
if (v == 0) {cout << 0 << "\n"; continue ;}
reverse(q.begin(), q.end());
cout << Get(st[v], fn[v], q) << "\n";
}
}
