#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
const int N = 2000001;
int n, m, trie[2][4 * N][4], cnt[2], mn[4 * N], mx[4 * N];
vector <int> f[4 * N];
vector <string> a;
int c(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
if(c == 'U') return 3;
assert(false);
}
void add(string &s, int idx, int tr){
int cur = 0;
for(auto &i : s){
if(trie[tr][cur][c(i)] == -1){
trie[tr][cur][c(i)] = ++cnt[tr];
}
cur = trie[tr][cur][c(i)];
if(tr == 0){
if(mn[cur] == -1) mn[cur] = idx;
mx[cur] = idx;
}
else{
f[cur].push_back(idx);
}
}
}
pair <int, int> query1(string &s){
int cur = 0;
for(auto &i : s){
if(trie[0][cur][c(i)] == -1){
return make_pair(-1, -1);
}
cur = trie[0][cur][c(i)];
}
return make_pair(mn[cur], mx[cur]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(trie, -1, sizeof trie);
memset(mn, -1, sizeof mn);
cin >> n >> m;
a.resize(n);
for(auto &i : a) cin >> i;
sort(a.begin(), a.end());
for(int i = 0 ; i < n ; i++){
add(a[i], i, 0);
reverse(a[i].begin(), a[i].end());
add(a[i], i, 1);
reverse(a[i].begin(), a[i].end());
}
for(int i = 0 ; i < m ; i++){
string l, r;
cin >> l >> r;
reverse(r.begin(), r.end());
auto q1 = query1(l);
int cur = 0;
for(auto &i : r){
if(trie[1][cur][c(i)] == -1){
q1 = make_pair(-1, -1);
break;
}
cur = trie[1][cur][c(i)];
}
if(q1.first == -1){
cout << "0\n";
continue;
}
auto &q2 = f[cur];
cout << upper_bound(q2.begin(), q2.end(), q1.second) - lower_bound(q2.begin(), q2.end(), q1.first) << "\n";
}
}
