#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =1e5+5;
const int maxm =2e6+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,Q,m[420];
int t[2][maxm][4],it[2],L[maxm],R[maxm];
string a[maxn];
vector<int> pos[maxm];
void add(int id,const string& s,int i,bool rev){
int u=1;
for (int j=0;j<s.size();j++) {
int c=m[(rev?s[s.size()-1-j]:s[j])];
if (!t[id][u][c]) t[id][u][c]=++it[id];
u=t[id][u][c];
if (id==0) {
if (!L[u]) L[u]=i;
R[u]=i;
}
else pos[u].push_back(i);
}
}
int get(int id,const string& s,bool rev) {
int u=1;
for (int j=0;j<s.size();j++) {
int c=m[(rev?s[s.size()-1-j]:s[j])];
u=t[id][u][c];
if (!u) return 0;
}
return u;
}
int main() {
// freopen("../input.inp","r",stdin);
// freopen("output.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
clock_t start,end;
start=clock();
m['A']=0;
m['G']=1;
m['C']=2;
m['U']=3;
cin >>n>>Q;
it[0]=it[1]=1;
for (int i=1;i<=n;i++) cin >>a[i];
sort(a+1,a+1+n);
for (int i=1;i<=n;i++) {
add(0,a[i],i,0);
add(1,a[i],i,1);
}
while (Q--) {
string p,q;
cin >>p>>q;
int u=get(0,p,0),v=get(1,q,1);
cout <<max(0,(int)(upper_bound(pos[v].begin(),pos[v].end(),R[u])-
lower_bound(pos[v].begin(),pos[v].end(),L[u])))<<'\n';
}
end=clock();
ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
cerr<<dur<<'\n';
return 0;
}
