#include <bits/stdc++.h>
using namespace std;
int get_val(char f) {
if (f == 'A') return 0;
if (f == 'G') return 1;
if (f == 'C') return 2;
return 3;
}
char get_char(int x) {
if (x == 0) return 'A';
if (x == 1) return 'G';
if (x == 2) return 'C';
return 'U';
}
const int NUMBEROFNODES = 2e6 + 5, INF = 1e9;
struct Trie{
struct Node{
int child[4], l, r;
} nodes[NUMBEROFNODES];
int cur;
int new_node() {
cur++;
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
nodes[cur].l = INF; nodes[cur].r = -INF;
return cur;
}
void add_string(string s, int id) {
int pos = 0;
for (auto f : s) {
int c = get_val(f);
if (nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node();
pos = nodes[pos].child[c];
nodes[pos].l = min(nodes[pos].l, id);
nodes[pos].r = max(nodes[pos].r, id);
}
}
pair<int, int> get_range(string s) {
int pos = 0;
for (auto f : s) {
int c = get_val(f);
if (nodes[pos].child[c] == -1) return {-1, -1};
pos = nodes[pos].child[c];
}
return {nodes[pos].l, nodes[pos].r};
}
};
struct ReversedTrie{
struct Node{
int child[4];
vector<int> ids;
} nodes[NUMBEROFNODES];
int cur;
int new_node() {
cur++;
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
nodes[cur].ids.clear();
return cur;
}
void add_string(string s, int id) {
reverse(s.begin(), s.end());
int pos = 0;
for (auto f : s) {
int c = get_val(f);
if (nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node();
pos = nodes[pos].child[c];
nodes[pos].ids.push_back(id);
}
}
int query(string s, pair<int, int> range) {
reverse(s.begin(), s.end());
int pos = 0;
for (auto f : s) {
int c = get_val(f);
if (nodes[pos].child[c] == -1) return 0;
pos = nodes[pos].child[c];
}
int l = lower_bound(nodes[pos].ids.begin(), nodes[pos].ids.end(), range.first) - nodes[pos].ids.begin();
int r = upper_bound(nodes[pos].ids.begin(), nodes[pos].ids.end(), range.second) - nodes[pos].ids.begin() - 1;
return r - l + 1;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector<string> v;
for(int i = 1; i <= n; i++){
string s; cin >> s;
v.push_back(s);
}
sort(v.begin(), v.end());
Trie trie1;
ReversedTrie trie2;
for(int i = 1; i <= n; i++){
trie1.add_string(v[i - 1], i);
trie2.add_string(v[i - 1], i);
}
while(m--){
string p, q; cin >> p >> q;
pair<int, int> range = trie1.get_range(p);
if (range.first == -1) cout << "0\n";
else cout << trie2.query(q, range) << "\n";
}
}
