#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
struct trie{
vi strings;
vector<trie*> cld;
trie(){
cld.assign(4, 0);
}
};
int size = 0;
void insert(trie* t, vi &s, int i){
//cout << i << endl;
if(i == s.size()){ t->strings.pb(size); return;}
auto &c = t->cld[s[i]];
t->strings.pb(size);
if(!c) c = new trie();
insert(c, s, i+1);
}
int cnt(trie *t, vi &s, int i, int l, int r){
if(i == s.size()){
//cout << "Counting ";
//for(int k : t->strings) cout << k << " ";
//cout << endl;
return lower_bound(t->strings.begin(), t->strings.end(), r)
- lower_bound(t->strings.begin(), t->strings.end(), l);
} else {
if(!t->cld[s[i]]) return 0;
return cnt(t->cld[s[i]], s, i+1, l, r);
}
}
struct modTrie{
int sz = 0;
vector<modTrie*> cld;
int l, r;
modTrie(){
cld.assign(16, 0);
}
};
void insert(modTrie* t, vi &s, int i){
if(i == s.size()){ t->sz++; return;}
auto &c = t->cld[s[i]];
if(!c) c = new modTrie();
insert(c, s, i+1);
}
trie *T, *revT;
vi S(0), revS(0);
void dfs(modTrie* t){
t->l = size;
//cout<<t->sz<<endl;
for(int i = 0; i < t->sz; i++) {
insert(T, S, 0);
insert(revT, revS, 0);
size++;
}
for (int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(t->cld[i + 4*j]) {
S.pb(i); revS.pb(j);
dfs(t->cld[i + 4*j]);
S.pop_back(); revS.pop_back();
}
t->r = size;
}
void getRange(modTrie* t, vi &s, int i, int &l, int &r){
if(i == s.size()){
l = t->l;
r = t->r;
} else {
if(!t->cld[s[i]]){
l = t->l;
r = t->l;
} else getRange(t->cld[s[i]], s, i+1, l, r);
}
}
int val[300];
int N, M;
modTrie* modT;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
val['A'] = 0;
val['G'] = 1;
val['C'] = 2;
val['U'] = 3;
cin >> N >> M;
modT = new modTrie();
T = new trie();
revT = new trie();
for(int i = 0; i < N; i++){
string s;
cin >> s;
vi S;
for(int j = 0; j < s.size(); j++){
S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
}
//cout << "Made S" << endl;
insert(modT, S, 0);
}
dfs(modT);
//cout << "Done " << endl;
for(int i = 0; i < M; i++){
string p, q;
cin >> p >> q;
reverse(q.begin(), q.end());
vi P, Q, S;
for(char c : p) P.pb(val[c]);
for(char c : q) Q.pb(val[c]);
for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
int l, r;
getRange(modT, S, 0, l, r);
//cout << "Range " << l << " " << r << endl;
//cout << "lowest sz " << S.size() << endl;
if(P.size() < Q.size()) {
cout << cnt(revT, Q, 0, l, r) << endl;
} else cout << cnt(T, P, 0, l, r) << endl;
}
}
/*
3 3
AA
AA
AGA
*/
