#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2000000;
const int P = 31;
const int mod = 1e9 + 9;
int pw[N+10];
int n, m;
vector<string> a;
vector<vector<int> > Hashings;
vector<int> turn_hash(string &s){
vector<int> h;
h.push_back(s[0]);
for(int i = 1;i < (int)s.size(); i++){
int pref = ((h.back() * P) % mod + s[i]) % mod;
h.push_back(pref);
}
return h;
}
int into(char ch){
if(ch == 'A') return 0;
if(ch == 'C') return 1;
if(ch == 'G') return 2;
return 3;
}
int vert = 1;
struct node{
vector<int> idx = {};
int nxt[4] = {-1, -1, -1, -1};
};
node trie[N * 2];
void add(string &s, int pos){
int cur = 0;
for(int i = 0;i < s.size(); i++){
int k = into(s[i]);
if(trie[cur].nxt[k] == -1) trie[cur].nxt[k] = vert++;
cur = trie[cur].nxt[k];
trie[cur].idx.push_back(pos);
}
}
int count(string &s, int l, int r){
int cur = 0;
for(int i = 0;i < (int)s.size(); i++){
int k = into(s[i]);
cur = trie[cur].nxt[k];
if(cur == -1) return 0;
}
vector<int> &v = trie[cur].idx;
int it = lower_bound(all(v), l) - v.begin();
int it1 = upper_bound(all(v), r) - v.begin();
return it1 - it;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
a.resize(n);
pw[0] = 1;
for(int i = 1;i <= N; i++){
pw[i] = (pw[i-1] * P) % mod;
}
vector< vector<int> > vece;
for(auto &e : a){
cin >> e;
vece.push_back(turn_hash(e));
}
vector<int> p;
for(int i = 0;i < n; i++) p.push_back(i);
auto get=[&](vector<int> &cur, int l, int r){
if(l == 0) return cur[r];
int all = (cur[r] - (cur[l-1] * pw[r-l+1]) % mod);
all = ((all % mod) + mod) % mod;
return all;
};
sort(all(p), [&](int i, int j){
if(a[i][0] != a[j][0]){
return into(a[i][0]) < into(a[j][0]);
}
int low = 0, high = min(a[i].size(), a[j].size());
while(high-low > 1){
int mid = (low + high) / 2;
if(get(vece[i], 0, mid) == get(vece[j], 0, mid)){
low = mid;
}else{
high = mid;
}
}
low++;
if(low >= (int)a[i].size() || low >= a[j].size()){
return a[i].size() < a[j].size();
}
return into(a[i][low]) < into(a[j][low]);
});
vector<string> aa = a;
a.clear();
for(int i : p){
a.push_back(aa[i]);
}
for(int i = 0;i < a.size(); i++){
string t = a[i];
// cout << a[i] << "\n";
reverse(all(t));
add(t, i);
}
//cout << '\n' << '\n';
while(m--){
string p, q; cin >> p >> q;
int l = 0, r = n-1;
for(int i = 0;i < p.size(); i++){
int lo = l-1, ro = r+1;
while(lo + 1 < ro){
int mid = (lo + ro) >> 1;
if(i + 1 <= a[mid].size() && a[mid][i] > p[i]){
ro = mid;
}else lo = mid;
}
int ss = ro-1;
lo = l-1, ro = r+1;
while(lo + 1 < ro){
int mid = (lo + ro) >> 1;
if(i + 1 > a[mid].size() || a[mid][i] < p[i]) lo = mid;
else ro = mid;
}
l = lo+1, r = ss;
if(l > r) break;
}
reverse(all(q));
//cout << p << " = " << l << ' ' << r << '\n';
cout << count(q, l, r) << '\n';
}
return 0;
}
