#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;
const int N = 1e5+5;
const int MOD = 1e9+7;
int n, q, timer = 0, timer1 = 0;
int pre[N][4], suf[N][4];
vector <int> bitpre[N * 4], bitsuf[N * 4];
string s[N];
string s1, s2;
int get(char c){
if (c == 'A') return 0;
if (c == 'G') return 1;
if (c == 'C') return 2;
return 3;
}
void addpre(string s,int i){
int node = 0;
for (char c : s){
int val = get(c);
if (!pre[node][val]) pre[node][val] = ++timer;
node = pre[node][val];
bitpre[node].push_back(i);
}
}
ii getpre(string s){
int node = 0;
for (char c : s){
int val = get(c);
if (!pre[node][val]) return {-1,-1};
node = pre[node][val];
}
return {bitpre[node][0],bitpre[node][(int)bitpre[node].size() - 1]};
}
void addsuf(string s,int i){
int node = 0;
for (char c : s){
int val = get(c);
if (!suf[node][val]) suf[node][val] = ++timer1;
node = suf[node][val];
bitsuf[node].push_back(i);
}
}
int getsuf(string s,int l,int r){
int node = 0;
for (char c : s){
int val = get(c);
if (!suf[node][val]) return 0;
node = suf[node][val];
}
int lo = lower_bound(bitsuf[node].begin(),bitsuf[node].end(),l) - bitsuf[node].begin();
int hi = upper_bound(bitsuf[node].begin(),bitsuf[node].end(),r) - bitsuf[node].begin();
return hi - lo;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> s[i];
sort(s+1,s+1+n);
for (int i = 1; i <= n; i++){
addpre(s[i],i);
reverse(s[i].begin(),s[i].end());
addsuf(s[i],i);
}
while (q--){
cin >> s1 >> s2;
ii res = getpre(s1);
if (res.fi == -1) cout << 0 << '\n';
else{
reverse(s2.begin(),s2.end());
cout << getsuf(s2,res.fi,res.se) << '\n';
}
}
return 0;
}
