/*
Bai nay ta khong can co dinh 2 vi tri, ta chi can co dinh 1 vi tri la du, vi tri con lai dung dem
--> rut ra: co bai ta can co dinh nhieu thuws thi thuwr coos dinhj 1 cais rooif cais kia dungf cachs naof
ddeer nos bieens maats ddi laf dduowcj
*/
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
using namespace std;
typedef long long ll;
const int N = 100002;
int id(char x){
if(x=='A') return 0;
if(x=='G') return 1;
if(x=='C') return 2;
if(x=='U') return 3;
}
int t1[2000002][4], t2[2000002][4], cnt1 = 1, cnt2 = 1, cnt = 0, low[N*20], high[N*20];
int n, q;
string s[N];
vector <vector <int> > v;
void add2(string cur){
int len = cur.size();
int u = 1;
f0(i, len){
char now = cur[i];
if(t2[u][id(now)]==0){
t2[u][id(now)] = ++cnt2;
}
u = t2[u][id(now)];
}
}
void add1(string cur, int e){
int len = cur.size();
int u = 1;
f0(i, len){
char now = cur[i];
if(t1[u][id(now)]==0){
t1[u][id(now)] = ++cnt1;
}
u = t1[u][id(now)];
v[u].emplace_back(e);
}
}
void dfs(int u, int p){
low[u] = ++cnt;
f0(i, 4){
if(t2[u][i]==0) continue;
dfs(t2[u][i], u);
}
high[u] = ++cnt;
}
int get_low(string cur){
int len = cur.size();
int u = 1;
f0(i, len){
u = t2[u][id(cur[i])];
}
return low[u];
}
int find1(string cur){
int len = cur.size();
int u = 1;
f0(i, len){
if(t1[u][id(cur[i])]==0) return 0;
u = t1[u][id(cur[i])];
}
return u;
}
pair <int, int> find2(string cur){
int len = cur.size();
int u = 1;
f0(i, len){
if(t2[u][id(cur[i])]==0) return {-1, -1};
u = t2[u][id(cur[i])];
}
return {low[u], high[u]};
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n >> q;
int dem = 0;
f1(i, n){
cin >> s[i];
dem += s[i].size();
reverse(s[i].begin(), s[i].end());
add2(s[i]);
}
v.resize(dem + 1);
dfs(1, 1);
f1(i, n){
int now = get_low(s[i]);
reverse(s[i].begin(), s[i].end());
add1(s[i], now);
}
f1(i, cnt1) sort(v[i].begin(), v[i].end());
while(q--){
string s1, s2;
cin >> s1;
cin >> s2;
reverse(s2.begin(), s2.end());
int g1 = find1(s1);
pair <int, int> cur = find2(s2);
if(g1==0 || cur.first==-1){
cout << 0 << "\n";
continue;
}
int k1 = lower_bound(v[g1].begin(), v[g1].end(), cur.first) - v[g1].begin();
int k2 = upper_bound(v[g1].begin(), v[g1].end(), cur.second) - v[g1].begin() - 1;
int res = k2 - k1 + 1;
res = max(res, 0);
cout << res << "\n";
}
}
