#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define FOR(i, j, n) for(ll i = j; i<= n; i++)
#define ROF(i, n, j) for(ll i = n; i>= j; i--)
#define pb push_back
#define F first
#define S second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define G(i, j) get<j-1>(i)
#define prll(x) cout << #x << ": " << x << endl;
const ll mn = 1e5 + 5, ms = 2e6 + 5, p = 1e6 + 3, mod = 1e9 + 7, mc = 6;
string a[mn];
pair<string, string> qu[mn];
ll pp[mn], h[mn];
unordered_map<ll, bool> mark;
set<pii> g[ms];
ll ans[mn];
struct Trie
{
struct Node
{
ll c[mc], num;
vector<ll> k, t;
}tmp;
ll n = 0;
vector<Node> node;
void add(ll id, ll ind, ll po)
{
string s = a[ind];
if (po == s.size())
{
ll tmp = (p*s[po-1])%mod;
if (mark[tmp]) node[id].k.pb(tmp);
ROF(i, po-2, 0)
{
tmp = (tmp*p)%mod;
tmp = (tmp+(s[i]*p)%mod)%mod;
if (mark[tmp]) node[id].k.pb(tmp);
}
return;
}
if (node[id].c[s[po]-'a'] == 0)
{
n++;
node.pb(tmp);
node[id].c[s[po]-'a'] = n;
}
add(node[id].c[s[po]-'a'], ind, po+1);
}
void add2(ll id, ll ind, ll po)
{
string s = qu[ind].F;
if (po == s.size())
{
node[id].t.pb(ind);
return;
}
if (node[id].c[s[po]-'a'] == 0)
{
return;
}
add2(node[id].c[s[po]-'a'], ind, po+1);
}
void ezaf(ll id, ll u, ll ted)
{
auto it = g[id].lower_bound({u, 0});
if (it == g[id].end() or (*it).F != u)
{
g[id].insert({u, ted});
}
else
{
ted += (*it).S;
g[id].erase(it);
g[id].insert({u, ted});
}
return;
}
void init(ll id)
{
FOR(i, 0, 3)
{
if (node[id].c[i] != 0) init(node[id].c[i]);
}
pii maxi = {node[id].k.size(), id};
FOR(i, 0, 3)
{
if (g[node[node[id].c[i]].num].size() > maxi.F)
{
maxi = {g[node[node[id].c[i]].num].size(), node[node[id].c[i]].num};
}
}
node[id].num = maxi.S;
for(auto u: node[id].k)
{
ezaf(node[id].num, u, 1);
}
FOR(i, 0, 3)
{
if (node[id].c[i] != 0 and node[node[id].c[i]].num != node[id].num)
{
auto it = g[node[node[id].c[i]].num].begin();
while (it != g[node[node[id].c[i]].num].end())
{
ezaf(node[id].num, (*it).F, (*it).S);
it++;
}
}
}
for(auto ind: node[id].t)
{
ll u = h[ind];
auto it = g[node[id].num].lower_bound({u, 0});
if (it == g[node[id].num].end() or (*it).F != u) continue;
ans[ind] = (*it).S;
}
}
}tr;
ll get_hash(string s)
{
ll tmp = 0;
FOR(i, 0, s.size()-1)
{
tmp = (tmp+(pp[i+1]*s[i])%mod)%mod;
}
return tmp;
}
signed main()
{
IOS;
tr.node.pb(tr.tmp);
ll n, q;
cin >> n >> q;
pp[0] = 1;
FOR(i, 1, max(n, q))
{
pp[i] = (pp[i-1]*p)%mod;
}
FOR(i, 1, n)
{
cin >> a[i];
FOR(j, 0, a[i].size()-1)
{
if (a[i][j] == 'A') a[i][j] = 'a';
if (a[i][j] == 'U') a[i][j] = 'b';
if (a[i][j] == 'G') a[i][j] = 'c';
if (a[i][j] == 'C') a[i][j] = 'd';
}
}
FOR(i, 1, q)
{
string s1, s2;
cin >> s1 >> s2;
FOR(j, 0, s1.size()-1)
{
if (s1[j] == 'A') s1[j] = 'a';
if (s1[j] == 'U') s1[j] = 'b';
if (s1[j] == 'G') s1[j] = 'c';
if (s1[j] == 'C') s1[j] = 'd';
}
FOR(j, 0, s2.size()-1)
{
if (s2[j] == 'A') s2[j] = 'a';
if (s2[j] == 'U') s2[j] = 'b';
if (s2[j] == 'G') s2[j] = 'c';
if (s2[j] == 'C') s2[j] = 'd';
}
qu[i] = {s1, s2};
h[i] = get_hash(s2);
mark[h[i]] = 1;
}
FOR(i,1 , n)
{
tr.add(0, i, 0);
}
FOR(i, 1, q)
{
tr.add2(0, i, 0);
}
tr.init(0);
FOR(i,1 , q)
{
cout << ans[i] << "\n";
}
return 0;
}
