#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 2;
const int M = 2e6 + 5;
const int mx = 2e6;
int n, m, cur = 0, cnt = 0;
string s[N];
int in[2][26 * N], out[2][26 * N];
int x[2][N], ans[N];
char xet[] = {'C', 'U', 'G', 'A'};
struct Node
{
int child[26];
vector<int> exist;
} nodes[2][26 * N];
vector<int> ask[26 * N];
int new_node(int hihi)
{
cur++;
memset(nodes[hihi][cur].child, -1, sizeof(nodes[hihi][cur].child));
return cur;
}
void add_string(string s, int j, int hihi)
{
int pos = 0;
for (int i = 0; i < s.size(); i++)
{
int c = s[i] - 'A';
if (nodes[hihi][pos].child[c] == -1)
nodes[hihi][pos].child[c] = new_node(hihi);
pos = nodes[hihi][pos].child[c];
}
nodes[hihi][pos].exist.push_back(j);
}
void dfs(int pos, int hihi)
{
in[hihi][pos] = out[hihi][pos] = ++cnt;
for (int i = 0; i < 4; i++)
{
int c = xet[i] - 'A';
if(nodes[hihi][pos].child[c] == -1)
continue;
dfs(nodes[hihi][pos].child[c], hihi);
}
out[hihi][pos] = cnt;
for(auto i : nodes[hihi][pos].exist)
x[hihi][i] = in[hihi][pos];
// cout << hihi << " " << pos << " " << in[hihi][pos] << '\n';
return;
}
pair<int, int> find_string(string s, int hihi)
{
int pos = 0;
for (int i = 0; i < s.size(); i++)
{
int c = s[i] - 'A';
if(nodes[hihi][pos].child[c] == -1)
return {-1,- 1};
pos = nodes[hihi][pos].child[c];
}
// cout << s << " " << hihi << " " << pos << '\n';
return {in[hihi][pos], out[hihi][pos]};
}
vector<int> vt[M];
vector<tuple<int, int, int>> add[M];
int bit[M];
int get(int p)
{
int idx = p, ans = 0;
while (idx > 0) {
ans += bit[idx];
idx -= (idx & (-idx));
}
return ans;
}
void update(int u, int v)
{
int idx = u;
while (idx <= mx)
{
bit[idx] += v;
idx += (idx & (-idx));
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(nodes[0][0].child, -1, sizeof(nodes[0][0].child));
for(int i = 1; i <= n; i++)
{
cin >> s[i];
add_string(s[i], i, 0);
}
dfs(0, 0);
cur = cnt = 0;
memset(nodes[1][0].child, -1, sizeof(nodes[1][0].child));
for(int i = 1; i <= n; i++)
{
reverse(s[i].begin(), s[i].end());
add_string(s[i], i, 1);
}
dfs(0, 1);
for(int i = 1; i <= n; i++)
vt[x[0][i]].push_back(x[1][i]);//, cout << x[0][i] << " " << x[1][i] << '\n';
memset(ans, -1, sizeof ans);
for(int i = 1; i <= m; i++)
{
string p, q;
cin >> p >> q;
reverse(q.begin(), q.end());
pair<int, int> tmp = find_string(p, 0), tmp1 = find_string(q, 1);
// cout << tmp.fi << " " << tmp.se << " " << tmp1.fi << " " << tmp1.se << '\n';
if(tmp.fi != -1 && tmp1.fi != -1)
{
add[tmp.fi - 1].push_back({tmp1.fi, tmp1.se, i});
add[tmp.se].push_back({tmp1.fi, tmp1.se, i});
}
}
for(int i = 1; i <= mx; i++)
{
for(auto j : vt[i])
update(j, 1);
for(auto [j, k, l] : add[i])
{
if(ans[l] == -1)
ans[l] = get(k) - get(j - 1);
else
ans[l] = get(k) - get(j - 1) - ans[l];
// cout << i << " " << j << " " << k << " " << ans[l] << '\n';
}
}
for(int i = 1; i <= m; i++)
if(ans[i] == -1)
cout << 0 << '\n';
else
cout << ans[i] << '\n';
return 0;
}
