#include <bits/stdc++.h>
#define name "rna"
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
#define ll long long
#define fi first
#define se second
#define ii pair <int, int>
#define sz(a) a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define MASK(x) (1ll << x)
#define bit(x, i) ((x >> i) & 1)
#define pop_count(x) __builtin_popcount(x)
#define mingdu signed main()
using namespace std;
const ll mod = 998244353;
void add(ll& a, ll b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
void mx(int& a, int b) {if (b > a) a = b;}
void mn(int& a, int b) {if (b < a) a = b;}
ll mul1(ll a, ll b) {
return ((a % mod) * (b % mod)) % mod;
}
ll mul2(ll a, ll b) {
ll res = 0;
while (b) {
if (b & 1) add(res, a);
add(a, a);
b >>= 1;
}
return res;
}
ll pw1(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = mul1(res, a);
a = mul1(a, a);
b >>= 1;
}
return res;
}
ll pw2(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = mul2(res, a);
a = mul2(a, a);
b >>= 1;
}
return res;
}
const int N = 1e6 + 5;
int n, q;
string s[N];
int change(char x) {
if (x == 'A') return 0;
if (x == 'C') return 1;
if (x == 'G') return 2;
return 3;
}
struct trie {
struct node {
node* child[4];
int l, r;
node() {
FOR(i, 0, 3) child[i] = 0;
l = 2e9, r = 0;
}
};
node* root;
trie() {
root = new node();
}
void add(const string& s, const int& cnt) {
int n = sz(s) - 1;
node* p = root;
FOR(i, 0, n) {
int x = change(s[i]);
if (!p -> child[x]) p -> child[x] = new node();
p = p -> child[x];
mx(p -> r, cnt);
mn(p -> l, cnt);
}
}
ii get(const string& s) {
int l, r;
int n = sz(s) - 1;
node* p = root;
FOR(i, 0, n) {
int x = change(s[i]);
if (!p -> child[x]) return {2e9, 2e9};
p = p -> child[x];
}
return {p -> l, p -> r};
}
};
struct rev_trie {
struct node {
node* child[4];
vector <int> id;
node() {
FOR(i, 0, 3) child[i] = 0;
id.clear();
}
};
node* root;
rev_trie() {
root = new node();
}
void add(string s, const int& cnt) {
reverse(s.begin(), s.end());
int n = sz(s) - 1;
node* p = root;
FOR(i, 0, n) {
int x = change(s[i]);
if (!p -> child[x]) p -> child[x] = new node();
p = p -> child[x];
p -> id.pb(cnt);
}
}
int get(const string &s, const ii& k) {
int l = k.fi, r = k.se;
if (l == r && l == 2e9) return 0;
int n = sz(s) - 1;
node* p = root;
FOR(i, 0, n) {
int x = change(s[i]);
if (!p -> child[x]) return 0;
p = p -> child[x];
}
return upper_bound(all(p -> id), r) - lower_bound(all(p -> id), l);
}
};
void nhap() {
cin >> n >> q;
FOR(i, 1, n) cin >> s[i];
}
void giai() {
trie tree1;
rev_trie tree2;
sort(s + 1, s + 1 + n);
FOR(i, 1, n) {
tree1.add(s[i], i);
tree2.add(s[i], i);
}
while (q--) {
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
cout << tree2.get(q, tree1.get(p)) << "\n";
}
}
mingdu {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
nhap();
giai();
return 0;
}
