#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(S) (int)(S).size()
const int NM = 1e5, MOD = 1e9+7, LOG = 17, inf = 1e9+7;
int N, M;
string P[2*NM+5], Q[2*NM+5];
vector <int> pref[2*NM+5], suff[2*NM+5];
int id_pref[2*NM+5], id_suff[2*NM+5], val[2*NM+5], pos[2*NM+5], bit[2*NM+5], ans[NM+5];
int c(char ch){
if (ch == 'A') return 0;
if (ch == 'G') return 1;
if (ch == 'C') return 2;
return 3;
}
void process(string &S, vector <int> &f){
f.resize(sz(S)+1);
f[0] = 0;
for (int i = 1; i <= sz(S); i++)
f[i] = ((ll)f[i-1]*4+c(S[i-1]))%MOD;
}
int lcp(vector <int> &f1, vector <int> &f2){
int l = 1, r = min(sz(f1), sz(f2))-1, res = 0;
while (l <= r){
int mid = (l+r)/2;
if (f1[mid] == f2[mid]){
res = mid;
l = mid+1;
}
else r = mid-1;
}
return res;
}
bool cmp_pref(int x, int y){
int res = lcp(pref[x], pref[y]);
if (res == min(sz(pref[x]), sz(pref[y]))-1){
return sz(pref[x]) < sz(pref[y]);
}
return c(P[x][res]) < c(P[y][res]);
}
bool cmp_suff(int x, int y){
int res = lcp(suff[x], suff[y]);
if (res == min(sz(suff[x]), sz(suff[y]))-1){
return sz(suff[x]) < sz(suff[y]);
}
return c(Q[x][res]) < c(Q[y][res]);
}
void update(int p, int v){
while (p <= N+M){
bit[p] += v;
p += p & (-p);
}
}
int sum(int p){
int res = 0;
while (p > 0){
res += bit[p];
p -= p & (-p);
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++){
cin >> P[i];
Q[i] = P[i];
reverse(Q[i].begin(), Q[i].end());
process(P[i], pref[i]);
process(Q[i], suff[i]);
}
for (int i = N+1; i <= N+M; i++){
cin >> P[i] >> Q[i];
reverse(Q[i].begin(), Q[i].end());
process(P[i], pref[i]);
process(Q[i], suff[i]);
}
for (int i = 1; i <= N+M; i++)
id_pref[i] = id_suff[i] = i;
sort(id_pref+1, id_pref+1+N+M, cmp_pref);
sort(id_suff+1, id_suff+1+N+M, cmp_suff);
for (int i = 1; i <= N+M; i++)
val[id_suff[i]] = i;
for (int i = 1; i <= N+M; i++)
pos[i] = val[id_pref[i]];
int curL = 1, curR = 0;
for (int i = 1; i <= N+M; i++){
if (id_pref[i] <= N) continue;
int k = sz(pref[id_pref[i]])-1, L = i, R = i;
int l = 1, r = i-1;
while (l <= r){
int mid = (l+r)/2;
if (lcp(pref[id_pref[mid]], pref[id_pref[i]]) >= k){
L = mid;
r = mid-1;
}
else l = mid+1;
}
l = i+1, r = N+M;
while (l <= r){
int mid = (l+r)/2;
if (lcp(pref[id_pref[i]], pref[id_pref[mid]]) >= k){
R = mid;
l = mid+1;
}
else r = mid-1;
}
while (curL > L){
curL--;
if (id_pref[curL] <= N) update(pos[curL], 1);
}
while (curR < R){
curR++;
if (id_pref[curR] <= N) update(pos[curR], 1);
}
while (curL < L){
if (id_pref[curL] <= N) update(pos[curL], -1);
curL++;
}
while (curR > R){
if (id_pref[curR] <= N) update(pos[curR], -1);
curR--;
}
k = sz(suff[id_suff[pos[i]]])-1;
int resl = pos[i], resr = pos[i];
l = 1, r = pos[i]-1;
while (l <= r){
int mid = (l+r)/2;
if (lcp(suff[id_suff[mid]], suff[id_suff[pos[i]]]) >= k){
resl = mid;
r = mid-1;
}
else l = mid+1;
}
l = pos[i]+1, r = N+M;
while (l <= r){
int mid = (l+r)/2;
if (lcp(suff[id_suff[pos[i]]], suff[id_suff[mid]]) >= k){
resr = mid;
l = mid+1;
}
else r = mid-1;
}
ans[id_pref[i]-N] = sum(resr)-sum(resl-1);
}
for (int i = 1; i <= M; i++)
cout << ans[i] << '\n';
return 0;
}
