#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
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MXN = 1e5+5;
ll mod[2] = {1000000007, 998244353};
using Hash = pair<ll, ll>;
Hash operator+(Hash A, Hash B) {
return Hash((A.X+B.X)%mod[0], (A.Y+B.Y)%mod[1]);
}
Hash operator*(Hash A, Hash B) {
return Hash(A.X*B.X%mod[0], A.Y*B.Y%mod[1]);
}
Hash P;
bool is_prime(int x) {
for(int i=2; i*i<=x; i++)
if(x%i==0)
return 0;
return 1;
}
void init_hash() {
P.X = rng()%200+100;
while(!is_prime(P.X)) P.X++;
P.Y = rng()%200+100;
while(P.X==P.Y || !is_prime(P.Y)) P.Y++;
}
Hash get_hash(string s) {
Hash res = Hash(0, 0);
for(int i=SZ(s)-1; i>=0; i--)
res = (res*P) + Hash{s[i], s[i]};
return res;
}
int O[256];
char O_[4];
int timer;
vector<int> ch[4], cnt, stt, fnt;
int new_vertex() {
for(int i=0; i<4; i++) ch[i].pb(0);
cnt.pb(0);
return SZ(cnt)-1;
}
void insert(string s) {
int v=0;
for(char c : s) {
if(!ch[O[c]][v]) ch[O[c]][v] = new_vertex();
v = ch[O[c]][v];
}
cnt[v]++;
}
void dfs(int v) {
stt[v] = timer++;
for(int i=0; i<4; i++)
if(ch[i][v])
dfs(ch[i][v]);
fnt[v] = timer;
}
void init_trie() {
stt.resize(SZ(cnt));
fnt.resize(SZ(cnt));
timer = 0;
dfs(0);
}
vector<pair<Hash, pii>> Q[MXN];
int n, m, ans[MXN];
void add(string p, string q, int i) {
int v=0;
for(char c : p) {
if(!ch[O[c]][v]) return;
v = ch[O[c]][v];
}
Q[fnt[v]-1].pb(Mp(get_hash(q), pii(1, i)));
Q[stt[v]-1].pb(Mp(get_hash(q), pii(-1, i)));
}
map<Hash, int> hmap;
string path;
void solve(int v=0) {
if(cnt[v]) {
Hash hs = Hash(0, 0);
for(int i=SZ(path)-1; i>=0; i--)
hmap[hs = (hs*P) + Hash(path[i], path[i])] += cnt[v];
}
for(auto x : Q[stt[v]])
ans[x.Y.Y] += x.Y.X*hmap[x.X];
for(int i=0; i<4; i++)
if(ch[i][v]) {
path.pb(O_[i]);
solve(ch[i][v]);
path.pop_back();
}
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
init_hash();
O_[0]='A'; O_[O['C'] = 1]='C'; O_[O['G'] = 2]='G'; O_[O['U'] = 3]='U';
cin >> n >> m;
string s;
new_vertex();
for(int i=0; i<n; i++) {
cin >> s;
insert(s);
}
init_trie();
string p, q;
for(int i=0; i<m; i++) {
cin >> p >> q;
add(p, q, i);
}
solve();
for(int i=0; i<m; i++)
cout << ans[i] << '\n';
return 0;
}
