#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define ll long long
const int mod = 676767677;
const ll inf = 1e18 + 500;
const long double EPS = 1e-10;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}
const int LOG = 21;
const int N = 2000010;
const int MAX = 2000010 * LOG;
int seg[4 * N];
struct Trie {
int cnt;
int nx[MAX][4];
int sz[MAX];
void init(){
cnt = 0;
}
int addnode() {
sz[cnt] = 0;
memset(nx[cnt], -1, sizeof(nx[cnt]));
return cnt++;
}
void add(int root, string &s) {
for (int i = s.size() - 1; i >= 0; i--) {
char c = s[i];
if (nx[root][c - 'A'] == -1)
nx[root][c - 'A'] = addnode();
root = nx[root][c - 'A'];
sz[root]++;
}
}
}t;
int n, m;
string a[N];
void build(int id, int tl, int tr) {
seg[id] = t.addnode();
for (int i = tl; i <= tr; i++)
t.add(seg[id], a[i]);
if (tl == tr) return;
int md = (tl + tr)/2;
build(2*id, tl, md);
build(2*id+1, md+1, tr);
}
int lower_bound(string &s) {
int l = 0, r = n - 1, ret = n;
while (l <= r) {
int md = (l + r) / 2;
if (s <= a[md].substr(0, s.size())) {
ret = md;
r = md - 1;
}else l = md + 1;
}
return ret;
}
int upper_bound(string &s) {
int l = 0, r = n - 1, ret = n;
while (l <= r) {
int md = (l + r) / 2;
if (s < a[md].substr(0, s.size())) {
ret = md;
r = md - 1;
}else l = md + 1;
}
return ret;
}
int get(int root, string &q) {
for (char c : q) {
if (t.nx[root][c - 'A'] == -1) return 0;
root = t.nx[root][c - 'A'];
}
return t.sz[root];
}
int get(int id, int tl, int tr, int l, int r, string &q) {
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) return get(seg[id], q);
int md = (tl + tr)/2;
return get(2*id, tl, md, l, r, q) + get(2*id+1, md+1, tr, l, r, q);
}
string conv(string s) {
for (char &c : s) {
if (c == 'C') c = 'B';
else if (c == 'G') c = 'C';
else if (c == 'U') c = 'D';
}
return s;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> a[i];
a[i] = conv(a[i]);
}
sort(a, a + n);
build(1, 0, n - 1);
while (m--) {
string p, q;
cin >> p >> q;
p = conv(p);
q = conv(q);
reverse(q.begin(), q.end());
int l = lower_bound(p);
int r = upper_bound(p) - 1;
if (l > r) {
cout << 0 << endl;
continue;
}
cout << get(1, 0, n - 1, l, r, q) << endl;
}
}
int main(){
FAST
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
