#include <bits/stdc++.h>
#define task "TEST"
#define task2 "A"
#define pl pair<ll, ll>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b, c) for (int i=a; i<=b; i+=c)
#define FORE(i, a, b, c) for (int i=a; i>=b; i+=c)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int Mod = 1e9+7;
const int maxn = 2e6;
const ll Inf = 3e9;
int n, m, s[128];
string str[maxn+1];
struct TrieNode {
struct TrieNode* childNode[4];
int wordCount = 0;
vector<int> res = {};
TrieNode() {
FOR(i, 0, 3, 1) childNode[i] = NULL;
}
};
void insert_key(TrieNode* root, string& key, int num) {
TrieNode* currentNode = root;
for (auto c : key) {
if (currentNode->childNode[s[c]] == NULL) {
TrieNode* newNode = new TrieNode();
currentNode->childNode[s[c]] = newNode;
}
currentNode = currentNode->childNode[s[c]];
currentNode->res.pb(num);
}
currentNode->wordCount++;
}
vector<int> search_key(TrieNode* root, string& key) {
TrieNode* currentNode = root;
for (auto c : key) {
if (currentNode->childNode[s[c]] == NULL)
return vector<int>();
currentNode = currentNode->childNode[s[c]];
}
return currentNode->res;
}
TrieNode* trie = new TrieNode;
TrieNode* revtrie = new TrieNode;
void Read()
{
s['A'] = 0, s['G'] = 1, s['C'] = 2, s['U'] = 3;
cin >> n >> m;
FOR(i, 1, n, 1) cin >> str[i];
sort(str + 1, str + n + 1);
FOR(i, 1, n, 1) {
insert_key(trie, str[i], i);
reverse(str[i].begin(), str[i].end());
insert_key(revtrie, str[i], i);
}
}
void Solve()
{
string left, right;
vector<int> L, R;
int l, r;
while (m--) {
cin >> left >> right;
reverse(right.begin(), right.end());
L = search_key(trie, left);
R = search_key(revtrie, right);
if (!L.size() or !R.size()) {
cout << 0 << '\n';
continue;
}
l = lower_bound(R.begin(), R.end(), L.front()) - R.begin();
r = upper_bound(R.begin(), R.end(), L.back()) - R.begin();
cout << r - l << '\n';
}
}
int main()
{
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; //Setup();
for (t=1; t--;)
{
Read(); Solve();
}
}
