#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define name "code"
using namespace std;
const int max_n= 1e5;
string s[max_n + 2];
int get_val(char c) {
if(c == 'A') return 0;
if(c == 'C') return 1;
if(c == 'G') return 2;
return 3;
}
char get_char(int x) {
if(x == 0) return 'A';
if(x == 1) return 'C';
if(x == 2) return 'G';
return 'U';
}
struct TRIE {
struct NODE {
NODE* child[4];
int l, r, exist;
NODE() {
for(int i= 0; i < 4; ++i) child[i]= NULL;
l= max_n, r= -1, exist= 0;
}
}* root;
TRIE() : root(new NODE()) {}
void add(string s) {
NODE* cur= root;
for(char c : s) {
int id= get_val(c);
if(cur -> child[id] == NULL) cur -> child[id]= new NODE();
cur= cur -> child[id];
}
++cur -> exist;
}
void add(string s, int p) {
NODE* cur= root;
for(char c : s) {
int id= get_val(c);
cur= cur -> child[id];
cur -> l= min(cur -> l, p);
cur -> r= max(cur -> r, p);
}
}
int idx;
string str;
void sort(NODE* cur) {
if(cur == root) idx= 0, str= "";
for(int i= 0; i < cur -> exist; ++i) s[idx++]= str;
for(int i= 0; i < 4; ++i)
if(cur -> child[i] != NULL) {
str.push_back(get_char(i));
sort(cur -> child[i]);
str.pop_back();
}
}
pii get(string s) {
NODE* cur= root;
for(char c : s) {
int id= get_val(c);
if(cur -> child[id] == NULL) return make_pair(-1, -1);
cur= cur -> child[id];
}
return make_pair(cur -> l, cur -> r);
}
} trie;
struct REV_TRIE {
struct NODE {
NODE* child[4];
vector<int> idx;
NODE() {
for(int i= 0; i < 4; ++i) child[i]= NULL;
}
}* root;
REV_TRIE() : root(new NODE()) {}
void add(string s, int p) {
NODE* cur= root;
reverse(s.begin(), s.end());
for(int c : s) {
int id= get_val(c);
if(cur -> child[id] == NULL) cur -> child[id]= new NODE();
cur= cur -> child[id];
(cur -> idx).push_back(p);
}
}
void build(NODE* cur) {
if((cur -> idx).size()) sort((cur -> idx).begin(), (cur -> idx).end());
for(int i= 0; i < 4; ++i) {
if(cur -> child[i] != NULL) build(cur -> child[i]);
}
}
int get(int l, int r, string s) {
if(l == -1) return 0;
NODE* cur= root;
reverse(s.begin(), s.end());
for(char c : s) {
int id= get_val(c);
if(cur -> child[id] == NULL) return 0;
cur= cur -> child[id];
}
int g= lower_bound((cur -> idx).begin(), (cur -> idx).end(), l) - (cur -> idx).begin();
int h= upper_bound((cur -> idx).begin(), (cur -> idx).end(), r) - (cur -> idx).begin();
return h - g;
}
} rev_trie;
void solve() {
int n, q; cin >> n >> q;
for(int i= 0; i < n; ++i) {
string t; cin >> t;
trie.add(t);
}
trie.sort(trie.root);
for(int i= 0; i < n; ++i) trie.add(s[i], i);
for(int i= 0; i < n; ++i) rev_trie.add(s[i], i);
rev_trie.build(rev_trie.root);
for(int i= 0; i < q; ++i) {
string p, q; cin >> p >> q;
auto [l, r]= trie.get(p);
cout << rev_trie.get(l, r, q) << '\n';
}
}
signed main() {
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
if(fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
int T= 1;
for(; T > 0; --T) solve();
return 0;
}
