#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define fi first
#define se second
#define ll long long
#define int long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
template <class X, class Y>
bool maximize(X &x, Y y) {
if(x < y) {
x = y;
return true;
}
return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if(x > y) {
x = y;
return true;
}
return false;
}
void solve();
int32_t main() {
#define task "test"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
solve();
}
const int N=1e5+5;
int n,m,tr[200];
string s[N];
struct Trie{
struct Node{
int ch[4],mn,mx;
Node(){
fill(begin(ch),end(ch),-1);
mn=1e9,mx=0;
}
};
vector<Node> t={Node()};
void ahihi(int num, int val){
t[num].mn=min(t[num].mn,val);
t[num].mx=max(t[num].mx,val);
}
void add_string(string &s, int id){
int p=0;
for(char c:s){
ahihi(p,id);
int ct=tr[c];
if(t[p].ch[ct]==-1){
t[p].ch[ct]=sz(t);
t.eb();
}
p=t[p].ch[ct];
}
ahihi(p,id);
}
ii getRange(string &s){
int p=0;
for(char c:s){
int ct=tr[c];
if(t[p].ch[ct]==-1) return {-1,-1};
p=t[p].ch[ct];
}
return {t[p].mn, t[p].mx};
}
} trie;
struct ReverseTrie{
struct Node{
int ch[4];
vector<int> ids;
Node(){
fill(begin(ch),end(ch),-1);
}
};
vector<Node> t={Node()};
void ahihi(int num, int val){
t[num].ids.eb(val);
}
void add_string(string &s, int id){
int p=0;
FORD(i,sz(s)-1,0){
ahihi(p,id);
int ct=tr[s[i]];
if(t[p].ch[ct]==-1){
t[p].ch[ct]=sz(t);
t.eb();
}
p=t[p].ch[ct];
}
ahihi(p,id);
}
int query(string &s, int L, int R){
int p=0;
FORD(i,sz(s)-1,0){
int ct=tr[s[i]];
if(t[p].ch[ct]==-1) return 0;
p=t[p].ch[ct];
}
int l=lower_bound(all(t[p].ids), L)-t[p].ids.begin(),
r=upper_bound(all(t[p].ids), R)-t[p].ids.begin();
return r-l;
}
} revtrie;
void solve() {
cin>>n>>m;
FOR(i,1,n) cin>>s[i];
sort(s+1,s+1+n);
tr['A']=0; tr['U']=1; tr['G']=2; tr['C']=3;
FOR(i,1,n){
trie.add_string(s[i],i);
revtrie.add_string(s[i],i);
}
FOR(i,1,m){
string p,q; cin>>p>>q;
ii range=trie.getRange(p);
cout<<revtrie.query(q,range.fi,range.se)<<'\n';
}
}
