#include <bits/stdc++.h>
///----------------[shorthand macros]---------------------------------------
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cast(a, b) static_cast<a>(b)
#define MASK(n) ((n >= 64 ? ~0ULL : ((1ULL << (n)) - 1ULL)))
#define BIT(n, i) (((n) >> (i)) & 1)
#define SET(n, i) (n = ((n) | (1 << (i))))
#define UNSET(n, i) (n = ((n) & ~(1 << (i))))
#define FLIP(n, i) (n = ((n) ^ (1 << (i))))
#define el '\n'
using namespace std;
///-------------[type aliases]------------------------------------
template <typename T>
using ve = vector<T>;
using ll = long long;
using ull = unsigned ll;
using db = double;
using vi = ve<int>;
using vll = ve<ll>;
using vdb = ve<db>;
using vb = ve<bool>;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
///--------------------[constants]------------------------------------------
const ll MAX = 1e6 + 7;
const ll MOD = 1e9 + 7;
const ll inf = 2e9 + 7;
const int MAX_NODE = 2e6 + 7;
int mp[256];
char d[4] = {'A', 'C', 'G', 'U'};
///---------------------[structs]-------------------------------------------
struct Trie
{
struct Node
{
Node* child[4];
int ext, l, r;
Node() : ext(0), l(inf), r(-inf)
{
for (int i = 0; i < 4; i++) child[i] = nullptr;
}
};
Node* root;
Trie()
{
root = new Node();
}
void add(const string& s, int id)
{
Node* p = root;
for (auto i : s)
{
int c = mp[i];
if (!p->child[c])
{
p->child[c] = new Node();
}
p = p->child[c];
p->l = min(p->l, id);
p->r = max(p->r, id);
}
p->ext++;
}
void str_sort(Node* p, string& str, ve<string>& res)
{
for (int i = 0; i < p->ext; i++)
res.pb(str);
for (int i = 0; i < 4; i++)
{
if (!p->child[i]) continue;
str += d[i];
str_sort(p->child[i], str, res);
str.pop_back();
}
}
ii get_range(const string& s)
{
Node* p = root;
for (auto i : s)
{
int c = mp[i];
if (!p->child[c]) return ii(-1, -1);
p = p->child[c];
}
return ii(p->l, p->r);
}
};
struct RevTrie
{
struct Node
{
Node* child[4];
vi id;
int ext;
Node() : ext(0)
{
for (int i = 0; i < 4; i++) child[i] = nullptr;
}
};
Node* root;
RevTrie()
{
root = new Node();
}
void add(const string& s, int id)
{
Node* p = root;
for (int i = s.size()-1; i >= 0; i--)
{
int c = mp[s[i]];
if (!p->child[c])
{
p->child[c] = new Node();
}
p = p->child[c];
p->id.pb(id);
}
p->ext++;
}
int query(string& s, ii range)
{
reverse(all(s));
Node* p = root;
for (auto i : s)
{
int c = mp[i];
if (!p->child[c]) return 0;
p = p->child[c];
}
auto l = lower_bound(all(p->id), range.fi);
auto r = upper_bound(all(p->id), range.se);
return r - l;
}
};
///---------------------[globals]-------------------------------------------
int n, m;
ve<string> vs;
Trie T;
RevTrie rT;
///-----------------[helper functions]--------------------------------------
void sort_strings(ve<string>& vs)
{
Trie voi;
while (!vs.empty())
{
voi.add(vs.back(), 0);
vs.pop_back();
}
string tmp;
voi.str_sort(voi.root, tmp, vs);
}
///------------------[main execution]---------------------------------------
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
mp['A'] = 0;
mp['C'] = 1;
mp['G'] = 2;
mp['U'] = 3;
cin >> n >> m;
vs.resize(n);
for (auto& i : vs) cin >> i;
sort_strings(vs);
for (int i = 0; i < n; i++)
{
T.add(vs[i], i);
rT.add(vs[i], i);
}
while (m--)
{
string s1, s2;
cin >> s1 >> s2;
ii r = T.get_range(s1);
int res = rT.query(s2, r);
cout << res << el;
}
return 0;
}
