#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
using namespace std;
const int INF = 1e9;
const int maxn = 2e6 + 7;
// ‘A’, ‘G’, ‘C’, ‘U’
// A B C D
struct node
{
int child[4];
node() {for(int i = 0; i < 4; i++) child[i] = -1;}
};
void modify(string &s)
{
for(int i = 0; i < s.size(); i++)
{
if(s[i] == 'G') s[i] = 'B';
else if(s[i] == 'U') s[i] = 'D';
}
}
vector <node> revtrie;
vector <node> nortrie;
vector <int> pos[maxn];
pii range[maxn];
string s[maxn];
int n , m;
void add_nor(string &s , int id)
{
int cur = 0;
for(char ch: s)
{
int c = ch - 'A';
if(nortrie[cur].child[c] == -1)
{
nortrie[cur].child[c] = nortrie.size();
nortrie.push_back(node());
}
cur = nortrie[cur].child[c];
range[cur].fi = min(range[cur].fi , id);
range[cur].se = max(range[cur].se , id);
}
}
void add_rev(string &s , int id)
{
int cur = 0;
for(char ch: s)
{
int c = ch - 'A';
if(revtrie[cur].child[c] == -1)
{
revtrie[cur].child[c] = revtrie.size();
revtrie.push_back(node());
}
cur = revtrie[cur].child[c];
pos[cur].push_back(id);
}
}
pii get_range(string &pre)
{
int cur = 0;
for(char ch: pre)
{
int c = ch - 'A';
if(nortrie[cur].child[c] == -1) return {-1 , -1};
cur = nortrie[cur].child[c];
}
return range[cur];
}
int counting(string &pre , string &suf)
{
int cur = 0;
pii rr = get_range(pre);
if(rr.fi == -1) return 0;
for(char ch: suf)
{
int c = ch - 'A';
if(revtrie[cur].child[c] == -1)
{
return 0;
}
cur = revtrie[cur].child[c];
}
return (int)(upper_bound(pos[cur].begin() , pos[cur].end() , rr.se) - pos[cur].begin())
- (int)(lower_bound(pos[cur].begin() , pos[cur].end() , rr.fi) - pos[cur].begin());
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> s[i]; modify(s[i]);
}
nortrie.push_back(node());
revtrie.push_back(node());
sort(s+1 , s+n+1);
range[0] = (pii){1 , n};
for(int i = 1; i < maxn; i++) range[i] = (pii){n+1 , 0};
for(int i = 1; i <= n; i++)
{
add_nor(s[i] , i);
reverse(s[i].begin() , s[i].end());
add_rev(s[i] , i);
}
for(int i = 0; i < maxn; i++)
{
sort(pos[i].begin() , pos[i].end());
}
for(int i = 1; i <= m; i++)
{
string pre , suf; cin >> pre >> suf;
reverse(suf.begin() , suf.end());
modify(pre); modify(suf);
cout << counting(pre , suf) << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("inp.txt" , "r" , stdin);
//freopen("out.txt" , "w" , stdout);
solve();
return 0;
}
