#include<bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define FOD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)
#define ll long long
#define ALL(a) a.begin(), a.end()
#define sz(a) a.size()
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define el "\n"
#define bit(a, x) (a >> x & 1)
#define X first
#define Y second
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define pb push_back
#define cntbit(x) __builtin_popcountll(x)
#define uni(a) sort(ALL(a)), a.resize(unique(ALL(a)) - a.begin())
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
const int maxn = 1e5 + 5;
string s[maxn];
int n, m;
int getint(char f) {
if (f == 'A') return 0;
if (f == 'G') return 1;
if (f == 'C') return 2;
return 3;
}
struct Trie{
struct Node{
Node* child[4];
int cnt, maxx, minn;
Node(){
FOR(i, 0, 3) child[i] = NULL;
maxx = -1e9;
minn = 1e9;
}
};
Node *root;
int cur;
Trie() : cur(0){
root = new Node();
};
void add(string s, int id){
Node* p = root;
for(auto f : s){
int c = getint(f);
if(p -> child[c] == NULL) p -> child[c] = new Node();
p = p -> child[c];
p -> maxx = max(p -> maxx, id);
p -> minn = min(p -> minn, id);
}
}
pii query(string s){
Node* p = root;
for(auto f : s){
int c = getint(f);
if(p -> child[c] == NULL) return {-1, -1};
p = p -> child[c];
}
return {p -> minn, p -> maxx};
}
} trie;
struct InTrie{
struct Node{
Node *child[4];
vi list;
Node (){
FOR(i, 0, 3) child[i] = NULL;
list.clear();
}
};
Node* root;
int cur;
InTrie() : cur(0){
root = new Node();
};
void add(string s, int id){
reverse(ALL(s));
Node* p = root;
for(auto f : s){
int c = getint(f);
if(p -> child[c] == NULL) p -> child[c] = new Node();
p = p -> child[c];
p -> list.pb(id);
}
}
int query(string s, pii range){
reverse(ALL(s));
Node* p = root;
for(auto f : s){
int c = getint(f);
if(p -> child[c] == NULL) return 0;
p = p -> child[c];
}
int l = lower_bound(ALL(p -> list), range.X) - p -> list.begin();
int r = upper_bound(ALL(p -> list), range.Y) - p -> list.begin() - 1;
return r - l + 1;
}
} trie1;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
FOR(i, 1, n) cin >> s[i];
sort(s + 1, s + n + 1);
FOR(i, 1, n){
trie.add(s[i], i);
trie1.add(s[i], i);
}
while(m--){
string p, q;
cin >> p >> q;
pii range = trie.query(p);
if(range.X == -1) cout << 0;
else cout << trie1.query(q, range);
cout << el;
}
cerr << "Time elapsed: " << TIME << " s" << el;
}
