#include <bits/stdc++.h>
#define name "test"
#define ll long long
#define fi first
#define se second
#define el '\n'
#define pback push_back
#define popback pop_back
#define pii pair <int, int>
#define plli pair <ll, int>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
const int N = 1e5 + 5;
const int MASK = (1 << 17);
const int base = 31;
const ll MOD = 1e9 + 7;
int n, m;
string s[N];
int cal(char c){
if(c == 'A') return 0;
if(c == 'U') return 1;
if(c == 'G') return 2;
return 3;
}
struct trie1 {
trie1 *child[4];
int l, r;
trie1() {
FOR(i, 0, 3) child[i] = NULL, l = 1e9, r = 0;
}
};
struct trie2 {
trie2 *child[4];
vector <int> id;
trie2() {
FOR(i, 0, 3) child[i] = NULL;
}
};
trie1 *root1;
trie2 *root2;
void add_pre(string s, int id) {
trie1 *p = root1;
FOR(i, 0, s.size() - 1) {
int x = cal(s[i]);
if (p -> child[x] == NULL) p -> child[x] = new trie1();
p = p -> child[x];
p -> l = min(p -> l, id);
p -> r = max(p -> r, id);
}
}
void add_suff(string s, int pos) {
reverse(s.begin(), s.end());
trie2 *p = root2;
FOR(i, 0, s.size() - 1) {
int x = cal(s[i]);
if (p -> child[x] == NULL) p -> child[x] = new trie2();
p = p -> child[x];
p -> id.pback(pos);
}
}
pii get_pre(string s) {
trie1 *p = root1;
FOR(i, 0, s.size() - 1) {
int x = cal(s[i]);
if (p -> child[x] == NULL) return {-1, -1};
p = p -> child[x];
}
return {p -> l, p -> r};
}
int get_suf(string s, pii d) {
int l = d.fi, r = d.se;
if (l == -1) return 0;
trie2 *p = root2;
FOR(i, 0, s.size() - 1) {
int x = cal(s[i]);
if (p -> child[x] == NULL) return 0;
p = p -> child[x];
}
vector <int> &b = p -> id;
return upper_bound(b.begin(), b.end(), r) - lower_bound(b.begin(), b.end(), l);
}
void dfs(trie2 *p) {
if (p == NULL) return;
sort(p -> id.begin(), p -> id.end());
FOR(i, 0, 3) if (p -> child[i]) dfs(p -> child[i]);
}
void input() {
cin >> n >> m;
root1 = new trie1();
root2 = new trie2();
FOR(i, 1, n) cin >> s[i];
sort(s + 1, s + n + 1);
FOR(i, 1, n) {
add_pre(s[i], i);
add_suff(s[i], i);
}
dfs(root2);
while (m--) {
string x, y;
cin >> x >> y;
reverse(y.begin(), y.end());
cout << get_suf(y, get_pre(x)) << el;
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
//
input();
//cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
return 0;
}
