#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#define hyathu main
#define popcorn __builtin_popcount
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int mmb = 1e5 + 69;
const ld pi = atan(1) * 4;
int n, m;
string s[mmb];
string p, q;
inline int getCode(char x){
switch(x){
case 'A': return 0;
case 'C': return 1;
case 'G': return 2;
case 'U': return 3;
}
}
struct TriePref{
struct Node{
vector <int> ids;
Node *ch[4];
Node(){fill(ch, ch + 4, nullptr);}
};
Node *root = new Node;
void insert(int id){
int l = s[id].length();
Node *cur = root;
for(int i = l - 1; i >= 0; --i){
int d = getCode(s[id][i]);
if(cur->ch[d] == nullptr)
cur->ch[d] = new Node;
cur = cur->ch[d];
cur->ids.push_back(id);
}
}
int countString(string &s, int l, int r){
Node *cur = root;
for(char i : s){
int d = getCode(i);
if(cur->ch[d] == nullptr)
return 0;
cur = cur->ch[d];
}
vector <int> &a = cur->ids;
return upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l);
}
} trp;
struct TrieSuf{
struct Node{
Node *ch[4];
int mn = 0, mx = 0;
Node(){fill(ch, ch + 4, nullptr);}
};
Node *root = new Node;
void insert(int id){
int l = s[id].length();
Node *cur = root;
for(int i = 0; i < l; ++i){
int d = getCode(s[id][i]);
if(cur->ch[d] == nullptr)
(cur->ch[d] = new Node)->mn = id;
cur = cur->ch[d];
cur->mx = id;
}
}
pair <int, int> searchRange(string &s){
Node *cur = root;
for(char i : s){
int d = getCode(i);
if(cur->ch[d] == nullptr)
return make_pair(0, 0);
cur = cur->ch[d];
}
return make_pair(cur->mn, cur->mx);
}
} trf;
void readData(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> s[i];
reverse(s[i].begin(), s[i].end());
}
sort(s + 1, s + n + 1);
}
void solve(){
for(int i = 1; i <= n; ++i){
trp.insert(i);
trf.insert(i);
}
for(int i = 1; i <= m; ++i){
cin >> p >> q;
reverse(q.begin(), q.end());
pair <int, int> rng = trf.searchRange(q);
cout << trp.countString(p, rng.first, rng.second) << "\n";
}
}
#define filename "test"
int hyathu(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifdef dangheo
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
#else
//freopen(filename".INP", "r", stdin);
//freopen(filename".OUT", "w", stdout);
#endif
readData();
solve();
return 0;
}
