#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const ll mod = 1e9 + 7;
const ll INF = 1e18;
//--------------------------------------------------------------------
const ll N = 1e5 + 10;
const ll C = 2e6 + 10;
ll n, m;
ll ans[N];
string T = "AGCU";
struct TRIE {
ll child[C][4], node;
ll st[C], en[C], timedfs;
ll add(string &s) {
ll u = 0;
FOR(i, 0, s.size() - 1) {
ll k = T.find(s[i]);
if(child[u][k] == 0) {
child[u][k] = ++node;
}
u = child[u][k];
}
return u;
}
void dfs(ll u) {
st[u] = ++timedfs;
FOR(i, 0, 3) {
if(child[u][i]) {
dfs(child[u][i]);
}
}
en[u] = timedfs;
}
ll get(string &s) {
ll u = 0;
FOR(i, 0, s.size() - 1) {
ll k = T.find(s[i]);
if(child[u][k] == 0) return -1;
u = child[u][k];
}
return u;
}
} trie1, trie2;
const ll maxbit = 2e6 + 2;
ll BIT[maxbit];
void update(ll x, ll val, ll n) {
while(x <= n) {
BIT[x] += val;
x += x & -x;
}
}
ll get(ll x) {
ll sum = 0;
while(x > 0) {
sum += BIT[x];
x -= x & -x;
}
return sum;
}
struct state {
ll l, r, id;
};
vector<ll> event_update[C];
vector<state> event_query[C];
void add_update(ll l, ll r) {
event_update[l].push_back(r);
}
void add_query(ll l, ll r, ll u, ll v, ll id) {
if(l > 1) event_query[l - 1].push_back({u, v, -id});
event_query[r].push_back({u, v, id});
}
pa ed[N];
void hbmt() {
cin >> n >> m;
FOR(i, 1, n) {
string s;
cin >> s;
ll u_l = trie1.add(s);
reverse(s.begin(), s.end());
ll u_r = trie2.add(s);
ed[i] = {u_l, u_r};
}
trie1.dfs(0);
trie2.dfs(0);
FOR(i, 1, n) {
add_update(trie1.st[ed[i].fi], trie2.st[ed[i].se]);
}
FOR(i, 1, m) {
string p, q;
cin >> p >> q;
ll u = trie1.add(p);
reverse(q.begin(), q.end());
ll v = trie2.add(q);
if(u == -1 || v == -1) {
ans[i] = 0;
continue;
}
add_query(trie1.st[u], trie1.en[u], trie2.st[v], trie2.en[v], i);
}
ll n1 = trie1.timedfs, n2 = trie2.timedfs;
FOR(i, 1, n1) {
for(auto e : event_update[i]) {
update(e, 1, n2);
}
for(auto &e : event_query[i]) {
ll l = e.l, r = e.r, id = e.id;
int c = 1;
if(id < 0) {
c = -1;
id = -id;
}
ans[id] += c * (get(r) - get(l - 1));
}
}
FOR(i, 1, m) {
cout << ans[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#define NAME "hbmt"
if(fopen(NAME".inp", "r")) {
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
//int t;cin>>t;while(t--)
hbmt();
return 0;
}
