/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed
/* GNU G++17 7.3.0: No long long for faster code
GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
#include <bits/stdc++.h>
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long
#define sz(a) (int)a.size()
#define pii pair<int,int>
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6
using namespace std;
struct Node1{
int child[4];
int l, r;
};
struct Node2{
int child[4];
vector<int> id;
};
vector<Node1> Trie1;
vector<Node2> Trie2;
void init1(int i) {
Node1 tmp;
memset(tmp.child, -1, sizeof(tmp.child));
tmp.l = i;
Trie1.push_back(tmp);
}
void init2() {
Node2 tmp;
memset(tmp.child, -1, sizeof(tmp.child));
Trie2.push_back(tmp);
}
void add(string& s, int id) {
int pos = 0;
for (auto i : s) {
int t;
if (i == 'A') t = 0;
else if (i == 'U') t = 1;
else if (i == 'G') t = 2;
else t = 3;
if (Trie1[pos].child[t] == -1) {
Trie1[pos].child[t] = sz(Trie1);
init1(id);
}
pos = Trie1[pos].child[t];
Trie1[pos].r = id;
}
reverse(s.begin(), s.end());
pos = 0;
for (auto i : s) {
int t;
if (i == 'A') t = 0;
else if (i == 'U') t = 1;
else if (i == 'G') t = 2;
else t = 3;
if (Trie2[pos].child[t] == -1) {
Trie2[pos].child[t] = sz(Trie2);
init2();
}
pos = Trie2[pos].child[t];
Trie2[pos].id.push_back(id);
}
}
pii range(string& s) {
int pos = 0;
for (auto i : s) {
int t;
if (i == 'A') t = 0;
else if (i == 'U') t = 1;
else if (i == 'G') t = 2;
else t = 3;
if (Trie1[pos].child[t] == -1) return {0, 0};
pos = Trie1[pos].child[t];
}
return {Trie1[pos].l, Trie1[pos].r};
}
int n, q;
string s[100005];
int get(string& s, pii p) {
reverse(s.begin(), s.end());
int pos = 0;
for (auto i : s) {
int t;
if (i == 'A') t = 0;
else if (i == 'U') t = 1;
else if (i == 'G') t = 2;
else t = 3;
if (Trie2[pos].child[t] == -1) return 0;
pos = Trie2[pos].child[t];
}
return upper_bound(Trie2[pos].id.begin(), Trie2[pos].id.end(), p.second) - lower_bound(Trie2[pos].id.begin(), Trie2[pos].id.end(), p.first);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("cf.inp", "r", stdin);
// freopen("cf.out", "w", stdout);
init1(0); init2();
cin >> n >> q;
for1(i,1,n) cin >> s[i];
sort(s + 1, s + n + 1);
for1(i,1,n) add(s[i], i);
while(q--) {
string pre, suf;
cin >> pre >> suf;
auto p = range(pre);
cout << get(suf, p) << "\n";
}
}
