#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;
//#define lc (id * 2)
//#define rc (lc + 1)
//#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
const int maxn = 2e7 + 10;
const int LOG = 33;
vector<int> mem[maxn];
string S[maxn];
int n, q, trieVt[2], nxt[2][maxn][5], l[maxn], r[maxn];
map<int, int> mp;
void add(int tp, int i, string s) {
if (tp)
reverse(all(s));
int cur = 0;
for (char chil : s) {
char c = mp[chil];
if (!nxt[tp][cur][c])
nxt[tp][cur][c] = ++trieVt[tp];
cur = nxt[tp][cur][c];
if (tp)
mem[cur].pb(i);
else {
if (!l[cur])
l[cur] = i;
r[cur] = i;
}
}
}
int get(string s, int tp) {
if (tp)
reverse(all(s));
int cur = 0;
for (char chil : s) {
char c = mp[chil];
if (!nxt[tp][cur][c])
return 0;
cur = nxt[tp][cur][c];
}
return cur;
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> S[i];
mp['A'] = 0;
mp['G'] = 1;
mp['C'] = 2;
mp['U'] = 3;
sort(S + 1, S + n + 1);
for (int i = 1; i <= n; i++) {
add(1, i, S[i]);
add(0, i, S[i]);
}
while (q--) {
string P, Q;
cin >> P >> Q;
int v = get(P, 0);
int u = get(Q, 1);
if (!u || !v) {
cout << 0 << '\n';
continue;
}
int pf1 = upper_bound(all(mem[u]), r[v]) - mem[u].begin();
int pf2 = lower_bound(all(mem[u]), l[v]) - mem[u].begin();
cout << pf1 - pf2 << '\n';
}
return 0;
}
