#include <bits/stdc++.h>
using namespace std;
#define int long long
#define num(c) (c > 'A') + (c > 'C') + (c > 'G') + (c > 'U')
template<class T> struct fenwick{
vector<T> a; int n, p=1<<30; T s;
fenwick(int N) : a(++(n=N)) {}
fenwick& operator[](int i){ p = i; return *this; }
void operator+=(T v){
for(++p; p<n; p+=p&-p) a[p] += v; }
void operator=(T v){ operator+=(v - operator()(p, p)); }
T operator()(int i){
for(s=0, ++i; i; i^=i&-i) s += a[i];
return s; }
T operator()(int l, int r){ return operator()(r) - operator()(l-1); }
int lower_bound(T v){
for(s=0, p=1<<21; p/=2; ) if(s+p<=n && a[s+p]<v) v -= a[s+=p];
return s;
}
};
const int LIM = (int)2e6+1;
array<int, 4> g[LIM];
int t0[LIM], t1[LIM], dfsTimer = -1;
void dfs(int u){
t0[u] = ++dfsTimer;
for(int &v : g[u]) if(v > 0) dfs(v);
t1[u] = dfsTimer;
}
bool comp(const string &x, const string &y, bool eq){ // <=
int a = x.size(), b = y.size();
for(int i=0; i<b; ++i){
if(i == a) return 1;
if(x[i] < y[i]) return 1;
if(x[i] > y[i]) return 0;
}
return eq;
}
bool comp1(const string &x, const string &y){ // >
int a = x.size(), b = y.size();
for(int i=0; i<b; ++i){
if(i == a) return 0;
if(x[i] < y[i]) return 0;
if(x[i] > y[i]) return 1;
}
return 0;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
// cout << comp("U", "G", 1) sp "ok" nl;
int n, m; cin >> n >> m;
string a[n];
int pos[n], ans[m];
pair<array<string, 2>, int> b[m];
for(auto &i : a) cin >> i;
for(int i=0; i<m; ++i){
cin >> b[i].first[0] >> b[i].first[1];
b[i].second = i;
}
sort(a, a+n);
sort(b, b+m);
int curr = 1;
for(int i=0; i<n; ++i){
reverse(a[i].begin(), a[i].end());
int u = 0;
for(auto &c : a[i]){
if(!g[u][num(c)]) g[u][num(c)] = curr++;
u = g[u][num(c)];
}
pos[i] = u;
reverse(a[i].begin(), a[i].end());
}
dfs(0);
fenwick<int> f(++dfsTimer);
int l = 0, r = 1;
f[t0[pos[0]]] += 1;
for(auto &i : b){
while(r < n && comp(a[r], i.first[0], 1)){
f[t0[pos[r]]] += +1;
++r;
}
while(l < r && comp(a[l], i.first[0], 0)){
f[t0[pos[l]]] += -1;
++l;
}
while(l < r && comp1(a[r-1], i.first[0])){
f[t0[pos[r-1]]] += -1;
--r;
}
int u = 0;
reverse(i.first[1].begin(), i.first[1].end());
for(auto &c : i.first[1]){
if(!g[u][num(c)]) g[u][num(c)] = curr++;
u = g[u][num(c)];
if(u < 0) break;
}
if(u >= 0) ans[i.second] = f(t0[u], t1[u]);
else ans[i.second] = 0;
}
for(int i : ans) cout << i << '\n';
}
