#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;
inline void fileIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
constexpr int N = 2e6 + 10;
constexpr int MOD = 1e9 + 7;
template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }
map<char , int> mp({{'A' , 0} , {'G' , 1} , {'C' , 2} , {'U' , 3}});
int n , m, cnt[2];
string s[N], h[N], q[N];
int nxt[2][N][4];
vector<pii> vec[N];
int st[N], en[N], tme;
void dfs1(int v) {
st[v] = tme++;
rep(i , 0 , 4)
if (nxt[0][v][i])
dfs1(nxt[0][v][i]);
en[v] = tme;
}
int sz[N], pos[N], res[N];
vi have[N];
int seg[N << 1];
inline void segClear(int v = 1) {
if (!seg[v]) return;
seg[v] = 0;
if ((v << 1) < (n << 1)) segClear(v << 1);
if ((v << 1 | 1) < (N << 1)) segClear(v << 1 | 1);
}
inline void segAdd(int pos) {
for (pos += cnt[0] + 1; pos; pos >>= 1)
seg[pos]++;
}
inline int segGet(int l , int r) { int res = 0;
for (l += cnt[0] + 1, r += cnt[0] + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += seg[l++];
if (r & 1) res += seg[--r];
}
return res;
}
void dfsAdd(int v) {
for (auto e : have[v])
segAdd(st[pos[e]]);
rep(i , 0 ,4) {
int u = nxt[1][v][i];
if (u)
dfsAdd(u);
}
}
void dfs2(int v) {
int mx = -1, id =-1;
rep(i , 0 , 4)
if (nxt[1][v][i] && smax(mx , sz[nxt[1][v][i]]))
id = i;
rep(i , 0 , 4) {
int u = nxt[1][v][i];
if (u && i != id) {
dfs2(u);
segClear();
}
}
if (~id)
dfs2(nxt[1][v][id]);
rep(i , 0 , 4) {
int u = nxt[1][v][i];
if (u && i != id)
dfsAdd(u);
}
for (auto e : have[v])
segAdd(st[pos[e]]);
for (auto e : vec[v])
res[e.second] = segGet(st[e.first] , en[e.first]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef LOCAL
// fileIO("forbidden1");
#endif
cin >> n >> m;
rep(i , 0 , n) {
cin >> s[i];
auto f = [i](int id) -> int {
int now = 0;
if (id == 1) sz[0]++;
for (auto e : s[i]) {
if (!nxt[id][now][mp[e]])
nxt[id][now][mp[e]] = ++cnt[id];
now = nxt[id][now][mp[e]];
if (id == 1) sz[now]++;
}
return now;
};
pos[i] = f(0);
reverse(all(s[i]));
have[f(1)].pb(i);
}
rep(i , 0 , m) {
cin >> h[i] >> q[i];
reverse(all(q[i]));
auto f = [](int id, string &st) -> int {
int now = 0;
for (auto e : st) {
if (!nxt[id][now][mp[e]]) return -1;
now = nxt[id][now][mp[e]];
}
return now;
};
int lid = f(0, h[i]);
int rid = f(1 ,q[i]);
if (!~min(lid , rid))
continue;
vec[rid].pb({lid , i});
}
dfs1(0);
dfs2(0);
rep(i , 0 , m)
cout << res[i] << '\n';
return 0;
}
