#include <bits/stdc++.h>
#define here cerr<<"=============================\n"
#define ll int
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define sz(a) (ll)(a.size())
#define pb push_back
#define llinf 100000000000000000LL
#define endl '\n'
#define pll pair<ll,ll>
#define all(a) a.begin(),a.end()
#define fi first
#define sc second
using namespace std;
#define maxn 8000005
#define maxx 30
ll n,q;
ll t[maxn][5];
ll t2[maxn],ls[maxn],rs[maxn];
ll L[maxn],L2[maxn],R[maxn],R2[maxn];
ll root,root2;
ll ti = 0,tsz = 1;
ll lid[maxn],rid[maxn];
ll in[maxn],out[maxn];
vector<ll> a[maxn];
vector<pll> v[maxn];
string ss[maxn];
map<char,ll> id;
void add(ll &v,string &s,ll i,ll d){
if(!v) v = ++tsz;
if(sz(s)==i||i==-1) return;
ll c = id[s[i]];
add(t[v][c],s,i+d,d);
}
void dfs(ll v){
in[v] = ++ti;
for(ll i = 0;i<4;i++){
if(!t[v][i]) continue;
dfs(t[v][i]);
}
out[v] = ti;
}
pll get(ll v,string &s,ll i,ll d){
if(sz(s)==i||i==-1) return {in[v],out[v]};
ll c = id[s[i]];
if(t[v][c]==0) return {-1,-2};
return get(t[v][c],s,i+d,d);
}
struct FenwickTree {
vector<int> bit; // binary indexed tree
int n;
FenwickTree(int n) {
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> a) : FenwickTree(a.size()) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
int sum(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
map<pair<pll,ll> ,ll> mp;
int main()
{
id['A'] = 0;
id['G'] = 1;
id['U'] = 2;
id['C'] = 3;
cin >> n >> q;
root = 1;
root2 = 1;
for(ll i = 1;i<=n;i++){
string s; cin >> ss[i];
s = ss[i];
add(root,s,0,1);
}
dfs(root);
root2 = ++tsz;
for(ll i = 1;i<=n;i++){
string s = ss[i];
add(root2,s,sz(s)-1,-1);
}
ti = 0;
dfs(root2);
ll mx = tsz;
for(ll i = 1;i<=n;i++){
string s = ss[i];
pll p = get(root,s,0,1);
lid[i] = p.fi;
p = get(root2,s,sz(s)-1,-1);
rid[i] = p.fi;
a[rid[i]].pb(lid[i]);
}
for(ll i = 1;i<=q;i++){
string s; cin >> s;
pll p = get(root,s,0,1);
cin >> s;
L[i] = p.fi,R[i] = p.sc;
p = get(root2,s,sz(s)-1,-1);
L2[i] = p.fi,R2[i] = p.sc;
v[L2[i]-1].pb({L[i],R[i]});
v[R2[i]].pb({L[i],R[i]});
}
tsz = 0;
FenwickTree f(mx);
for(ll i = 0;i<=mx;i++){
for(ll x : a[i]){
f.add(x,1);
}
for(pll p : v[i]){
mp[{{p.fi,p.sc},i}] = f.sum(p.fi,p.sc);
}
}
for(ll i = 1;i<=q;i++){
cout<<mp[{{L[i],R[i]},R2[i]}] - mp[{{L[i],R[i]},L2[i]-1}]<<endl;
}
}
