#include <bits/stdc++.h>
#define ll int
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll N = 2e6 + 8;
struct trie{
ll t[N][4];
ll tin[N], tout[N];
ll lst = 1, tiktak;
ll z(char ch){
ll x;
if(ch == 'A') x = 0;
else if(ch == 'G') x = 1;
else if(ch == 'C') x = 2;
else x = 3;
return x;
}
void add(ll cur, ll id, string &s){
if(id == s.size()) return;
ll x = z(s[id]);
if(t[cur][x] == 0) t[cur][x] = ++lst;
add(t[cur][x], id + 1, s);
}
ll get(ll cur, ll id, string &s){
if(id == s.size()) return cur;
ll x = z(s[id]);
return get(t[cur][x], id + 1, s);
}
void dfs(ll v){
tin[v] = ++tiktak;
for(ll i=0;i<4;i++){
if(t[v][i] == 0) continue;
dfs(t[v][i]);
}
tout[v] = ++tiktak;
}
}t, rt;
struct seg{
ll t[N * 4];
ll n;
void upd(ll v, ll tl, ll tr, ll pos, ll val){
if(tl > pos || tr < pos) return;
if(tl == tr){
t[v] += val;
return;
}
ll tm = (tl + tr) / 2;
upd(v * 2, tl, tm, pos, val);
upd(v * 2 + 1, tm + 1, tr, pos, val);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void upd(ll pos, ll val){
upd(1, 1, n, pos, val);
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
if(tl > r || tr < l) return 0;
if(l <= tl && tr <= r) return t[v];
ll tm = (tl + tr) / 2;
return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}
ll get(ll l, ll r){
return get(1, 1, n, l, r);
}
}st;
void solve() {
ll i, j;
ll n, m;
cin>>n>>m;
string s[n];
for(i=0;i<n;i++){
cin>>s[i];
t.add(1, 0, s[i]);
reverse(all(s[i]));
rt.add(1, 0, s[i]);
reverse(all(s[i]));
}
vector<string> p(m), q(m);
for(i=0;i<m;i++){
cin>>p[i]>>q[i];
t.add(1, 0, p[i]);
reverse(all(q[i]));
rt.add(1, 0, q[i]);
}
t.dfs(1);
rt.dfs(1);
vector<array<ll, 2>> v;
vector<array<ll, 4>> sq;
set<ll> sx = {-1}, sy = {-1};
for(i=0;i<n;i++){
ll x = t.get(1, 0, s[i]);
reverse(all(s[i]));
ll y = rt.get(1, 0, s[i]);
reverse(all(s[i]));
v.pb({t.tin[x], rt.tin[y]});
sx.ins(t.tin[x]);
sy.ins(rt.tin[y]);
}
for(i=0;i<m;i++){
ll x = t.get(1, 0, p[i]);
ll y = rt.get(1, 0, q[i]);
sq.pb({t.tin[x], t.tout[x], rt.tin[y], rt.tout[y]});
sx.ins(t.tin[x] - 1);
sx.ins(t.tin[x]);
sx.ins(t.tout[x]);
sy.ins(rt.tin[y] - 1);
sy.ins(rt.tin[y]);
sy.ins(rt.tout[y]);
}
map<ll,ll> pos, pp;
ll c = 0, c2 = 0;
for(auto i : sx) pos[i] = ++c;
for(auto i : sy) pp[i] = ++c2;
vector<ll> ans(m + 5);
vector<vector<ll>> add(c2 + 5);
vector<vector<array<ll, 4>>> qq(c2 + 5);
st.n = c;
for(i=0;i<n;i++){
v[i][0] = pos[v[i][0]];
v[i][1] = pp[v[i][1]];
add[v[i][1]].pb(v[i][0]);
}
for(i=0;i<m;i++){
sq[i][0] = pos[sq[i][0]];
sq[i][1] = pos[sq[i][1]];
sq[i][2] = pp[sq[i][2]];
sq[i][3] = pp[sq[i][3]];
qq[sq[i][2] - 1].pb({sq[i][0], sq[i][1], -1, i});
qq[sq[i][3]].pb({sq[i][0], sq[i][1], 1, i});
}
for(i=0;i<=c2;i++){
for(auto j : add[i]){
st.upd(j, 1);
}
for(auto [l, r, c, id] : qq[i]){
ans[id] += st.get(l, r) * c;
}
}
for(i=0;i<m;i++){
cout<<ans[i]<<endl;
}
}
signed main(){
start();
ll t = 1;
//cin>>t;
while(t--) solve();
}
/*
*/
