/*
()_() ()_()
( o.o ) ( -.- )
> ^ < (")(")
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
#define ff(i, a, b, j) for (int i = (a), bb = (b), jj = (j); i <= bb; i += jj)
#define rf(i, a, b, j) for (int i = (a), bb = (b), jj = (j); i >= bb; i -= jj)
#define lshift(x, i) ((x) << (i))
#define rshift(x, i) ((x) >> (i))
#define checkbit(x, i) (((x) >> (i)) & 1ll)
#define cnt_bit1(x) __builtin_popcountll((x))
#define clz(x) __builtin_clzll((x)) // count leading zeros
#define ctz(x) __builtin_ctzll((x)) // count trailing zeros
#define ll long long
#define ull unsigned long long
#define ld long double
#define db double
#define pi acos(-1)
#define maxn 100005
#define mod 1000000007
int real(char c) {
if (c == 'A') {
return 0;
}
else if (c == 'C') {
return 1;
}
else if (c == 'G') {
return 2;
}
return 3;
}
char fake(int k) {
if (k == 0) {
return 'A';
}
else if (k == 1) {
return 'C';
}
else if (k == 2) {
return 'G';
}
return 'U';
}
string arr_string[maxn];
struct prefixTrie {
struct Node {
Node* child[4];
int l, r, isEnd;
Node() {
memset(child, NULL, sizeof child);
l = 1e9;
r = -1e9;
isEnd = 0;
}
};
Node* root;
int timeDFS;
prefixTrie() {
root = new Node();
timeDFS = 0;
}
void Add(string s) {
Node* cur = root;
for (auto c : s) {
int k = real(c);
if (cur->child[k] == NULL) {
cur->child[k] = new Node();
}
cur = cur->child[k];
}
cur->isEnd += 1;
return;
}
pii Find(string s) {
Node* cur = root;
for (auto c : s) {
int k = real(c);
if (cur->child[k] == NULL) {
return {1e9, -1e9};
}
cur = cur->child[k];
}
return {cur->l, cur->r};
}
void DFS(Node* cur, string s) {
if (cur->isEnd) {
cur->l = cur->r = ++timeDFS;
arr_string[timeDFS] = s;
ff (i, 2, cur->isEnd, 1) {
cur->r = ++timeDFS;
arr_string[timeDFS] = s;
}
}
ff (k, 0, 3, 1) {
if (cur->child[k] != NULL) {
DFS(cur->child[k], s + fake(k));
cur->l = min(cur->l, cur->child[k]->l);
cur->r = max(cur->r, cur->child[k]->r);
}
}
return;
}
};
struct suffixTrie {
struct Node {
Node* child[4];
vector<int> Vector;
bool check_sort;
Node() {
memset(child, NULL, sizeof child);
check_sort = false;
}
};
Node* root;
suffixTrie() {
root = new Node();
}
void Add(string s, int id) {
reverse(s.begin(), s.end());
Node* cur = root;
cur->Vector.push_back(id);
for (auto c : s) {
int k = real(c);
if (cur->child[k] == NULL) {
cur->child[k] = new Node();
}
cur = cur->child[k];
cur->Vector.push_back(id);
}
return;
}
int Find(string s, int l, int r) {
reverse(s.begin(), s.end());
Node* cur = root;
for (auto c : s) {
int k = real(c);
if (cur->child[k] == NULL) {
return 0;
}
cur = cur->child[k];
}
if (cur->check_sort) {
cur->check_sort = true;
sort(cur->Vector.begin(), cur->Vector.end());
}
int L = lower_bound(cur->Vector.begin(), cur->Vector.end(), l) - cur->Vector.begin();
int R = upper_bound(cur->Vector.begin(), cur->Vector.end(), r) - cur->Vector.begin();
return R - L;
}
};
int n, m;
prefixTrie pTrie;
suffixTrie sTrie;
void input() {
cin >> n >> m;
ff (i, 1, n, 1) {
string s;
cin >> s;
pTrie.Add(s);
}
return;
}
void solve() {
pTrie.DFS(pTrie.root, "");
ff (i, 1, n, 1) {
sTrie.Add(arr_string[i], i);
}
while (m--) {
string prefix, suffix;
cin >> prefix >> suffix;
pii p = pTrie.Find(prefix);
if (p.fi == 1e9 && p.se == -1e9) {
cout << 0 << '\n';
continue;
}
cout << sTrie.Find(suffix, p.fi, p.se) << '\n';
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int test_case = 1;
// cin >> test_case;
ff (i, 1, test_case, 1) {
input();
solve();
}
return 0;
}
/*
()_() ()_()
( o.o ) ( -.- )
> ^ < (")(")
*/
