#include <bits/stdc++.h>
#define ll int
#define INF (ll)1e9+1
#define bit(mask, id) ((mask >> id) & 1LL)
#define pb push_back
#define el '\n'
#define ft first
#define sc second
#define ii pair<ll,ll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, l, r) for(int i = (l); i >= (r); --i)
#define str string
#define all(a,i) memset(a,i,sizeof(a))
#define al(a) a.begin(),a.end()
/////////////////////////////
const long long oo = 1e18;
const int N = 2e5 + 9;
using namespace std;
struct TRIE{
struct Node{
ll l,r;
vector<ll>exist;
Node* child[4];
Node(){
l = INF, r = 0;
FOR(i,0,3) child[i] = NULL;
}
};
Node* root;
TRIE(){
root = new Node();
}
void add(str &s, ll id)
{
Node* pos = root;
for(auto x:s)
{
ll c = x-'A';
if(pos->child[c]==NULL)
{
pos->child[c] = new Node();
}
pos = pos->child[c];
pos->l = min(pos->l,id);
pos->r = max(pos->r,id);
pos->exist.pb(id);
}
}
bool fi(str &s)
{
Node* pos = root;
for(auto x:s)
{
ll c = x-'A';
if(pos->child[c]==NULL) return 0;
pos = pos->child[c];
}
return 1;
}
vector<ll>suffix(str &s)
{
vector<ll>ans;
if(!fi(s)) return ans;
Node* pos = root;
for(auto x:s)
{
ll c = x-'A';
pos = pos->child[c];
}
return pos->exist;
}
ii prefix(str &s)
{
if(!fi(s)) return {0,0};
Node* pos = root;
for(auto x:s)
{
ll c = x-'A';
pos = pos->child[c];
}
return {pos->l, pos->r};
}
};
TRIE pre, suf;
str a[N];
ll n,Q;
void en(str &s)
{
for(auto &x:s)
{
if(x=='G') x='B';
else if(x=='U') x='D';
}
}
ll Count(vector<ll>&v, ll l, ll r)
{
if(v.empty() || l==0 || r==0) return 0;
ll L = lower_bound(al(v),l)-v.begin();
ll R = upper_bound(al(v),r)-v.begin();
return R-L;
}
signed main()
{
#define TASK "rna"
if(fopen(TASK ".inp","r")) {
freopen (TASK ".inp","r",stdin);
freopen (TASK ".out","w",stdout);
//freopen (TASK ".ans","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>Q;
FOR(i,1,n) cin>>a[i], en(a[i]);
sort(a+1,a+1+n);
FOR(i,1,n)
{
pre.add(a[i],i);
str t = a[i];
reverse(al(t));
suf.add(t,i);
}
FOR(i,1,Q)
{
str p,q; cin>>p>>q;
en(p);
en(q);
reverse(al(q));
auto [l,r] = pre.prefix(p);
vector<ll>ans = suf.suffix(q);
cout<<Count(ans,l,r)<<el;
}
return 0;
}
