/*
thisiscaau's code
trying my best for a better future
*/
#include <bits/stdc++.h>
#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
using namespace std;
#define ll int
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<ll,ll> ii;
ll const mod = 1e9 + 7, MAXN = 3e6 + 5;
ll encode (char c){
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
if (c == 'U') return 3;
return 69696;
}
struct node {
ll child[4];
vector<ll> idx;
} trie[MAXN];
void gen (ll id){
memset(trie[id].child,-1,sizeof(trie[id].child));
}
ll triesize = 0;
void push(string s,ll id){
ll p = 0;
for (int i = 0 ; i < s.size() ; i++){
char c = s[i];
if (trie[p].child[encode(c)] == -1){
gen(++triesize);
trie[p].child[encode(c)] = triesize;
}
p = trie[p].child[encode(c)];
trie[p].idx.pb(id);
}
}
ll query (string s,ll l,ll r){
ll p = 0;
for (int i = 0 ; i < s.size() ; i++){
char c = s[i];
p = trie[p].child[encode(c)];
}
return lower_bound(trie[p].idx.begin(),trie[p].idx.end(),r) - lower_bound(trie[p].idx.begin(),trie[p].idx.end(),l);
}
ll tc,n,m;
string a[100005],suf[100005];
void aurelion_sol(){
// solution goes here
cin >> n >> m;
for (int i = 1 ; i <= n ; i++){
cin >> a[i];
}
sort(a + 1,a + n + 1);
for (int i = 1 ; i <= n ; i++){
suf[i] = a[i];
reverse(suf[i].begin(),suf[i].end());
}
gen(0);
for (int i = 1 ; i <= n ; i++){
push(suf[i],i);
}
while (m--){
string p,q; cin >> p >> q;
reverse(q.begin(),q.end());
ll lf,rt;
lf = lower_bound(a + 1,a + n + 1,p) - a;
p[p.size() - 1]++;
rt = upper_bound(a + 1,a + n + 1,p) - a;
cout << query(q,lf,rt) << endl;
}
}
signed main() {
#ifdef thisiscaau
fileopen("input", "output");
#endif
#ifndef thisiscaau
// fileopen1("LAH");
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
tc = 1;
while (tc--) aurelion_sol();
}
