#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxN = 1e6+5;
int n;
map<char, int> mp;
void pre(){
mp['A'] = 1;
mp['C'] = 2;
mp['G'] = 3;
mp['T'] = 4;
}
struct Trie {
struct Node {
Node* child[5][5];
int pre = 0;
int is_word = 0;
Node(){
memset(child, 0, sizeof(child));
}
};
Node* root;
Trie(){
root = new Node;
}
int count(string pre, string suf){
Node* cur = root;
int n = pre.size();
int m = suf.size();
for(int i =0; i<m; ++i){
int x = mp[pre[i]];
int y = mp[suf[i]];
if(!cur->child[x][y])
return 0;
cur = cur->child[x][y];
}
queue<pair<Node*, int>> q;
q.push(make_pair(cur, m));
int ans = 0;
while(q.size()){
auto u = q.front();
q.pop();
Node* cur = u.first;
int idx = u.second;
if(idx==n){
ans+=cur->pre;
continue;
}
for(int i =0; i<4; ++i){
if(cur->child[mp[pre[idx]]][i]){
Node*z = cur->child[mp[pre[idx]]][i];
q.push(make_pair(z, idx+1));
}
}
}
return ans;
}
void insert(const string &word){
Node* cur = root;
cur -> pre++;
int n = word.size();
for(int i =0; i<n; ++i){
int x = mp[word[i]];
int y = mp[word[n-i-1]];
if(! cur -> child[x][y])
cur -> child[x][y] = new Node;
cur = cur -> child[x][y];
cur -> pre++;
}
cur -> is_word++;
}
};
void doWork() {
int m;
cin >> n >> m;
Trie tr1, tr2;
for(int i =0; i<n; ++i){
string s;
cin >> s;
tr1.insert(s);
reverse(s.begin(), s.end());
tr2.insert(s);
}
while(m--){
string pref, suf;
cin >> pref >> suf;
if(pref.size()>suf.size()){
reverse(suf.begin(), suf.end());
cout << tr1.count(pref, suf) << '\n';
}
else{
reverse(pref.begin(), pref.end());
cout << tr2.count(suf, pref) << '\n';
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
pre();
int tt = 1;
// cin >> tt;
while (tt--) doWork();
return 0;
}
