#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int mp[257], id[N * 4][4], cnt[N * 4], timer = 0;
void init (){
mp['A'] = 0;
mp['C'] = 1;
mp['G'] = 2;
mp['U'] = 3;
timer = 1;
for (int i = 0; i < 4 * N; ++i){
cnt[i] = 0;
for (int j = 0; j < 4; ++j){
id[i][j] = 0;
}
}
return;
}
void ins (string &s, int i = 0, int cur = 1){
++cnt[cur];
if (i == s.size()){
return;
}
if (!id[cur][mp[s[i]]]){
id[cur][mp[s[i]]] = ++timer;
}
ins(s, i + 1, id[cur][mp[s[i]]]);
return;
}
int get (string &s, int i, int cur, bool pref, bool current){
if (i == s.size() || cur == 0){
return cnt[cur] * current;
}
int ans = 0, sum = 0;
for (int j = 0; j < 4; ++j){
sum += cnt[id[cur][j]];
}
ans = cnt[cur] - sum;
if (pref == true){
for (int j = 0; j < mp[s[i]]; ++j){
ans += cnt[id[cur][j]];
}
}
return ans + get(s, i + 1, id[cur][mp[s[i]]], pref, current);
}
int n, m, res[N];
string s[N], a[N], b[N];
vector<pair<int, int>> que[N];
int32_t main (){
ios::sync_with_stdio(false); cin.tie(nullptr);
if (fopen ("test.inp", "r")){
freopen ("test.inp", "r", stdin);
freopen ("test.out", "w", stdout);
}
init();
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> s[i];
ins(s[i]);
}
sort(s + 1, s + n + 1);
for (int i = 1; i <= m; ++i){
cin >> a[i] >> b[i];
reverse(b[i].begin(), b[i].end());
int l = get(a[i], 0, 1, true, false);
int r = get(a[i], 0, 1, true, true);
que[l].push_back({-1, i});
que[r].push_back({1, i});
}
init();
for (int i = 1; i <= n; ++i){
reverse(s[i].begin(), s[i].end());
ins(s[i]);
for (auto [x, y] : que[i]){
res[y] += x * get(b[y], 0, 1, false, true);
}
}
for (int i = 1; i <= m; ++i){
cout << res[i] << "\n";
}
}
