//holasoydember:D
//20/01/2024
#include <bits/stdc++.h>
#define pb push_back
#define all(n) n.begin(),n.end()
#define Z size()
#define S second
#define F first
#define ll long long
#define fo(x, y, z) for(ll x=y; x<=z; x++)
#define of(x, y, z) for(ll x=y; x>=z; x--)
using namespace std;
void value(int in){cout<<((in)?"YES\n":"NO\n");return;}
const ll md=1e9+7, mod=998244353, N=500005;
ll n, m, k, xd, zd;
ll a[N], b[N], tp[4][4][N], d[10];
string ss[N];
//set<ll> f, g;
vector<ll> v[N];
//queue<pair<ll,ll>> q;
ll ch(char c) {
if (c=='A') return 0;
if (c=='C') return 1;
if (c=='G') return 2;
return 3;
}
void add(string s, ll j, ll h, ll f){
k=1;
fo(i,0,s.Z-1){
ll c;
if(f==1)c=ch(s[s.Z-i-1]);
else c=ch(s[i]);
if(tp[h][c][k]==0)tp[h][c][k]=d[h]++;
k=tp[h][c][k];
if(h==0){
if(a[k]==0)a[k]=j;
b[k]=max(b[k],j);
}
else v[k].push_back(j);
}
return;
}
ll get(string s, ll h, ll f) {
k=1;
fo(i,0,s.Z-1){
ll c;
if (f==1)c=ch(s[s.Z-i-1]);
else c=ch(s[i]);
k=tp[h][c][k];
if (k==0)return 0;
}
return k;
}
void CD(){
cin>>n>>m;
d[0]=d[1]=2;
fo(i,0,n-1)cin>>ss[i];
sort(ss, ss+n);
fo(x,0,n-1) {
add(ss[x],x+1,0,0);
add(ss[x],x+1,1,1);
}
fo(x,0,m-1){
string s, t;
cin>>s>>t;
ll h=get(s, 0, 0), k=get(t, 1, 1);
ll g=lower_bound(v[k].begin(), v[k].end(), a[h])-v[k].begin(), l=upper_bound(v[k].begin(), v[k].end(), b[h])-v[k].begin();
cout<<max(0ll, l-g)<<"\n";
}
return;
}
int main()
{
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int t=1;
//cin>>t;
while(t--){
CD();
}
return 0;
}
