#include<bits/stdc++.h>
#define ll long long
#define pr pair <int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e6 + 5;
int n, m, pos[30];
string s[N];
struct Trie1
{
int child[N][4], sta[N], en[N], cnt = 0;
void make_trie ()
{
for (int i = 1; i < N; i++)
{
sta[i] = 1e9+5;
en[i] = 0;
}
}
void add (string &s, int idx)
{
int u = 0;
for (int i = 0; i < s.length(); i++)
{
int k = pos[s[i] - 'A'];
if (child[u][k] == 0)
child[u][k] = ++cnt;
u = child[u][k];
sta[u] = min(idx, sta[u]);
en[u] = max(idx, en[u]);
}
sta[u] = min(idx, sta[u]);
en[u] = max(idx, en[u]);
}
pr get (string &s)
{
int u = 0;
for (int i = 0; i < s.length(); i++)
{
int k = pos[s[i] - 'A'];
if (child[u][k] != 0)
u = child[u][k];
else
return {-1, -1};
}
return {sta[u], en[u]};
}
} trie1;
struct Trie2
{
int child[N][4], cnt = 0;
vector <int> id[N];
void add (string &s, int idx)
{
int u = 0;
for (int i = 0; i < s.length(); i++)
{
int k = pos[s[i] - 'A'];
if (child[u][k] == 0)
child[u][k] = ++cnt;
u = child[u][k];
id[u].push_back(idx);
}
}
int get (string &s, int l, int r)
{
int u = 0;
for (int i = 0; i < s.length(); i++)
{
int k = pos[s[i] - 'A'];
if (child[u][k] != 0)
u = child[u][k];
else
return 0;
}
int L = lower_bound(id[u].begin(), id[u].end(), l) - id[u].begin();
int R = upper_bound(id[u].begin(), id[u].end(), r) - id[u].begin() - 1;
return (R - L + 1);
}
} trie2;
void inp()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
}
void solve()
{
pos[0] = 0;
pos['G' - 'A'] = 1;
pos['C' - 'A'] = 2;
pos['U' - 'A'] = 3;
trie1.make_trie();
sort(s + 1, s + n + 1);
// for (int i = 1; i <= n; i++)
// cout << s[i] << "\n";
for (int i = 1; i <= n; i++)
{
trie1.add(s[i], i);
reverse(s[i].begin(), s[i].end());
trie2.add(s[i], i);
}
for (int i = 1; i <= m; i++)
{
string s1, s2;
cin >> s1 >> s2;
reverse(s2.begin(), s2.end());
pr pre = trie1.get(s1);
if (pre.fi == -1)
cout << 0;
else
{
cout << trie2.get(s2, pre.fi, pre.se);
}
cout << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);
inp();
solve();
}
