// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "RNA"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 2e5 + 5;
int numString, numQuery;
string str[N];
int id(char chr) {
if (chr == 'A') return 0;
if (chr == 'G') return 1;
if (chr == 'U') return 2;
return 3;
}
class Trie {
private:
struct Node {
Node *child[4];
int minIndex, maxIndex;
Node() {
REP(i, 4) child[i] = NULL;
minIndex = inf;
maxIndex = -inf;
}
};
Node *root;
public:
Trie() {
root = new Node();
}
void add(string s, int index) {
Node *p = root;
for(char chr : s) {
int pos = id(chr);
if (p -> child[pos] == NULL) p -> child[pos] = new Node();
p = p -> child[pos];
minimize(p -> minIndex, index);
maximize(p -> maxIndex, index);
}
}
ii query(string s) {
Node *p = root;
for(char chr : s) {
int pos = id(chr);
if (p -> child[pos] == NULL) return mp(-1, -1);
p = p -> child[pos];
}
return mp(p -> minIndex, p -> maxIndex);
}
} trie;
class Trie_reverse {
private:
struct Node {
Node *child[4];
vector<int> indexs;
Node() {
REP(i, 4) child[i] = NULL;
indexs.clear();
}
};
Node *root;
public:
Trie_reverse() {
root = new Node();
}
void add(string s, int index) {
Node *p = root;
for(char chr : s) {
int pos = id(chr);
if (p -> child[pos] == NULL) p -> child[pos] = new Node();
p = p -> child[pos];
p -> indexs.pb(index);
}
}
int query(string s, ii range) {
Node *p = root;
for(char chr : s) {
int pos = id(chr);
if (p -> child[pos] == NULL) p -> child[pos] = new Node();
p = p -> child[pos];
}
if ((p -> indexs).empty()) return 0;
int L = lower_bound(all((p -> indexs)), range.first) - (p -> indexs).begin();
int R = upper_bound(all((p -> indexs)), range.second) - (p -> indexs).begin();
return R - L;
}
} trie_rev;
void init(void) {
cin >> numString >> numQuery;
FOR(i, 1, numString) cin >> str[i];
sort(str + 1, str + numString + 1);
FOR(i, 1, numString) {
trie.add(str[i], i);
reverse(all(str[i]));
trie_rev.add(str[i], i);
}
}
void process(void) {
string prefix, suffix;
while(numQuery--) {
cin >> prefix >> suffix;
reverse(all(suffix));
ii range = trie.query(prefix);
cout << (range.fi != -1 ? trie_rev.query(suffix, range) : 0) << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) {
init();
process();
}
return 0;
}
