#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define lb(s, a) lower_bound(all(s), (a)) - s.begin()
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int ar = 2e6+5;
const ll mod = 1e9+7;
const int oo = 1e9;
int n, m, maxx = 0, maxy = 0;
int cs(char a) {
if(a == 'C') return 0;
if(a == 'U') return 1;
if(a == 'G') return 2;
return 3;
}
struct Trie {
struct Node{
int child[5];
} nodes[ar];
int cur;
Trie() : cur(0) {
memset(nodes[0].child, -1, sizeof(nodes[cur].child));
};
int new_node() {
cur++;
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
return cur;
}
void add(string s) {
int pos = 0;
for (auto f : s) {
int c = cs(f);
if (nodes[pos].child[c] == -1) {
nodes[pos].child[c] = new_node();
}
pos = nodes[pos].child[c];
}
}
int trace(string s) {
int pos = 0;
for (auto f : s) {
int c = cs(f);
pos = nodes[pos].child[c];
}
return in[pos];
}
int in[ar], out[ar], timeDfs = 0;
void dfs(int u) {
in[u] = ++timeDfs;
for(int i = 0; i < 4; ++i) if(nodes[u].child[i] != -1)
dfs(nodes[u].child[i]);
out[u] = timeDfs;
}
ii get(string s) {
int pos = 0;
for (auto f : s) {
int c = cs(f);
if (nodes[pos].child[c] == -1)
return {-1, -1};
pos = nodes[pos].child[c];
}
return {in[pos], out[pos]};
}
} t1, t2;
int bit[ar], res[ar], L[ar];
vector <int> x[ar];
struct Query {
int l, r, i;
bool t;
};
vector <Query> query[ar];
string s[100005];
void update(int i, int val) {
for(; i <= maxy; i += i & -i)
bit[i] += val;
}
int get(int i) {
if(i == 0) return 0;
int res = 0;
for(; i > 0; i -= i & -i)
res += bit[i];
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "b"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> s[i];
t1.add(s[i]);
string tmp = s[i];
reverse(all(tmp));
t2.add(tmp);
}
t1.dfs(0);
t2.dfs(0);
for(int i = 1; i <= n; ++i) {
string tmp = s[i];
reverse(all(tmp));
int tmp1 = t1.trace(s[i]), tmp2 = t2.trace(tmp);
x[tmp1].push_back(tmp2);
// cout << i << ' ' << tmp1 << ' ' << tmp2 << '\n';
}
string p, q;
for(int i = 1; i <= m; ++i) {
cin >> p >> q;
ii p1 = t1.get(p);
if(p1.fi == -1) continue;
reverse(all(q));
ii p2 = t2.get(q);
if(p2.fi == -1) continue;
// cout << i << ' ' << p1.fi << ' ' << p1.se << ' ' << p2.fi << ' ' << p2.se << '\n';
// if(p1.fi > p2.fi) swap(p1.fi, p2.fi);
// if(p1.se > p2.se) swap(p2.se, p1.se);
query[p1.fi - 1].push_back({p2.fi, p2.se, i, 0});
query[p1.se].push_back({p2.fi, p2.se, i, 1});
maxx = max({maxx, p1.se});
maxy = max({maxy, p2.se});
}
for(int i = 1; i <= maxx; ++i) {
for(auto y : x[i])
update(y, 1);
for(auto [l, r, j, t] : query[i]) {
int tmp = get(r) - get(l - 1);
if(t == 0) L[j] = tmp;
else res[j] = tmp - L[j];
}
}
for(int i = 1; i <= m; ++i)
cout << res[i] << '\n';
}
