#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;
int mp[256];
char d[4] = {'A', 'C', 'G', 'U'};
///---------------------[structs]-------------------------------------------
struct Node
{
Node* child[4];
int ext;
int st, w_cnt;
Node() : ext(0), st(0), w_cnt(0)
{
for (int i = 0; i < 4; i++) child[i] = nullptr;
}
};
struct Trie
{
Node* root;
int dfs_t;
Trie() : dfs_t(0)
{
root = new Node();
}
void add(const string& s)
{
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->ext++;
}
void sort_strings(Node* p, string& str, ve<string>& res)
{
p->w_cnt = p->ext;
p->st = dfs_t;
dfs_t += p->ext;
for (int i = 0; i < p->ext; i++)
{
res.pb(str);
// us[str] = res.size();
}
for (int i = 0; i < 4; i++)
{
if (!p->child[i]) continue;
str += d[i];
sort_strings(p->child[i], str, res);
str.pop_back();
p->w_cnt += p->child[i]->w_cnt;
}
}
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->st, p->st + p->w_cnt - 1);
}
};
struct RevTrie
{
Node* root;
RevTrie()
{
root = new Node();
}
void add(const string& s)
{
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->ext++;
}
bool get_all_suffix(
Node* p, string& s, int i,
string& str, ve<string>& res
)
{
if (i < s.size())
{
int c = mp[s[i]];
if (!p->child[c]) return false;
str += s[i];
get_all_suffix(p->child[c], s, i+1, str, res);
}
else
{
for (int j = 0; j < p->ext; j++)
{
res.pb(str);
}
for (int i = 0; i < 4; i++)
{
if (!p->child[i]) continue;
str += d[i];
get_all_suffix(p->child[i], s, inf, str, res);
str.pop_back();
}
if (i != inf)
for (auto& j : res) reverse(all(j));
return true;
}
}
};
///---------------------[globals]-------------------------------------------
int n, m;
Trie T;
RevTrie rT;
///-----------------[helper functions]--------------------------------------
///------------------[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);
// preprocess
mp['A'] = 0;
mp['C'] = 1;
mp['G'] = 2;
mp['U'] = 3;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string s; cin >> s;
T.add(s);
rT.add(s);
}
ve<string> sus;
string tmp;
T.sort_strings(T.root, tmp, sus);
while (m--)
{
string s1, s2;
cin >> s1 >> s2;
reverse(all(s2));
ii r = T.get_range(s1);
ve<string> hcm;
tmp = "";
bool f1 = rT.get_all_suffix(rT.root, s2, 0, tmp, hcm);
// cout << r.fi << ' ' << r.se << el;
// cout << f1 << el;
// for (auto i : hcm) cout << i << el;
//
// cout << el;
if (r.fi == -1 || !f1)
{
cout << 0 << el;
continue;
}
int cnt = 0;
for (auto i : hcm)
{
int id = lower_bound(all(sus), i) - sus.begin();
if (id >= r.fi && id <= r.se) cnt++;
}
cout << cnt << el;
}
return 0;
}
