#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")
using ll = long long;
using pii = pair<int, int>;
#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define Mp make_pair
#define all(x) x.begin(), x.end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MXN = 2e6+5;
int O[256];
char O_[4];
struct trie {
vector<int> ch[4], cnt, sz;
int new_vertex() {
for(int i=0; i<4; i++) ch[i].pb(0);
cnt.pb(0);
sz.pb(0);
return SZ(cnt)-1;
}
void insert(string s) {
int v=0;
sz[v]++;
for(char c : s) {
if(!ch[O[c]][v]) ch[O[c]][v] = new_vertex();
v = ch[O[c]][v];
sz[v]++;
}
cnt[v]++;
}
int get(string s) {
int v=0;
for(char c : s) {
if(!ch[O[c]][v]) return 0;
v = ch[O[c]][v];
}
return sz[v];
}
} T1, T2;
int timer;
vector<int> stt, fnt;
void dfs(int v) {
stt[v] = timer++;
for(int i=0; i<4; i++)
if(T1.ch[i][v])
dfs(T1.ch[i][v]);
fnt[v] = timer;
}
void init_trie() {
stt.resize(SZ(T1.cnt));
fnt.resize(SZ(T1.cnt));
timer = 0;
dfs(0);
}
vector<pair<string, pii>> Q[MXN];
int n, m, ans[MXN];
void add(string p, string q, int i) {
int v=0;
for(char c : p) {
if(!T1.ch[O[c]][v]) return;
v = T1.ch[O[c]][v];
}
reverse(all(q));
Q[fnt[v]-1].pb(Mp(q, pii(1, i)));
Q[stt[v]-1].pb(Mp(q, pii(-1, i)));
}
string path;
void solve(int v=0) {
if(T1.cnt[v]) {
reverse(all(path));
for(int i=0; i<T1.cnt[v]; i++)
T2.insert(path);
reverse(all(path));
}
for(auto x : Q[stt[v]])
ans[x.Y.Y] += x.Y.X*T2.get(x.X);
for(int i=0; i<4; i++)
if(T1.ch[i][v]) {
path.pb(O_[i]);
solve(T1.ch[i][v]);
path.pop_back();
}
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
O_[0]='A'; O_[O['C'] = 1]='C'; O_[O['G'] = 2]='G'; O_[O['U'] = 3]='U';
cin >> n >> m;
string s;
T1.new_vertex();
for(int i=0; i<n; i++) {
cin >> s;
T1.insert(s);
}
init_trie();
string p, q;
for(int i=0; i<m; i++) {
cin >> p >> q;
add(p, q, i);
}
T2.new_vertex();
solve();
for(int i=0; i<m; i++)
cout << ans[i] << '\n';
return 0;
}
