#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
using namespace std;
unordered_map <char, int> enhash = {
{'A', 0},
{'U', 1},
{'G', 2},
{'C', 3}
};
vector <char> dehash = {
'A', 'U', 'G', 'C'
};
const int lim = 1e5;
struct trie {
int free_node = 1;
vector <array <int, 4> > tree;
vector <int> str_node;
vector <char> node_col;
vector <int> in;
vector <int> out;
trie (int num_str) {
tree.resize (lim + 1);
str_node.resize (num_str + 1);
node_col.resize (lim + 1);
node_col[0] = '.';
};
void add (string str, int ind) {
int node = 0;
for (int i = 0; i < str.size(); i++) {
if (tree[node][enhash[str[i]]] == 0) {
node_col[free_node] = str[i];
tree[node][enhash[str[i]]] = free_node++;
}
node = tree[node][enhash[str[i]]];
}
str_node[ind] = node;
}
int traverse (string str) {
int node = 0;
for (int i = 0; i < str.size(); i++) {
if (tree[node][enhash[str[i]]] == 0)
return -1;
node = tree[node][enhash[str[i]]];
}
return node;
}
void calc_dfs () {
in.clear();
out.clear();
in.resize (lim + 1);
out.resize (lim + 1);
int timer = 0;
function <void(int,int)> dfs =
[&](int p, int par)->void {
in[p] = out[p] = ++timer;
for (int& e : tree[p])
if (e != par && e != 0)
dfs (e, p);
out[p] = timer;
};
dfs (0, 0);
}
void debug () {
function <void(int,int,int)> dfs =
[&](int p, int par, int dep)->void {
cout << string (dep, '\t') << node_col[p] << ' ' << in[p] << ' ' << out[p] << '\n';
for (int& e : tree[p])
if (e != par && e != 0)
dfs (e, p, dep + 1);
};
dfs (0, 0, 0);
}
};
int main () {
int N = 0, Q = 0;
cin >> N >> Q;
vector <string> in (N + 1);
for (int i = 1; i <= N; i++)
cin >> in[i];
trie preftrie (N + 1);
trie sufftrie (N + 1);
for (int i = 1; i <= N; i++) {
preftrie.add (in[i], i);
sufftrie.add ([](string str)->string {
reverse (str.begin(), str.end());
return str;
}(in[i]), i);
}
preftrie.calc_dfs();
sufftrie.calc_dfs();
// preftrie.debug();
// sufftrie.debug();
vector <pair <int, int> > status (N + 1);
for (int i = 1; i <= N; i++)
status[i] = {
preftrie.in[preftrie.str_node[i]],
sufftrie.in[sufftrie.str_node[i]]
};
while (Q--) {
string a = "", b = "";
cin >> a >> b;
reverse (b.begin(), b.end());
int prefnode = preftrie.traverse (a);
int suffnode = sufftrie.traverse (b);
if (prefnode == -1 || suffnode == -1) {
cout << 0 << '\n';
continue;
}
int& L1 = preftrie.in[prefnode], R1 = preftrie.out[prefnode];
int& L2 = sufftrie.in[suffnode], R2 = sufftrie.out[suffnode];
int ans = 0;
for (int i = 1; i <= N; i++)
if (L1 <= status[i].first && status[i].first <= R1)
if (L2 <= status[i].second && status[i].second <= R2)
ans++;
cout << ans << '\n';
}
}
