// #pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define tiii tuple<int,int,int>
using namespace std;
int conv(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
else return 3;
}
struct TrieNodePr{
int marked = false;
vector<vector<int>> child;
int markedSub = 0;
TrieNodePr(){
child.resize(4, vector<int>(4, -1));
}
};
struct TrieNode{
int marked = false;
vector<int> child;
int markedSub = 0;
TrieNode(){
child.resize(4, -1);
}
};
vector<TrieNodePr> triePr(1);
vector<TrieNode> trieP(1);
vector<TrieNode> trieS(1);
void insertPr(string& s, int l, int r, int ind = 0){
if(l == s.size()) {
triePr[ind].marked++;
triePr[ind].markedSub++;
return;
}
int cl = conv(s[l]);
int cr = conv(s[r]);
if(triePr[ind].child[cl][cr] == -1){
triePr[ind].child[cl][cr] = triePr.size();
triePr.push_back(TrieNodePr());
}
int ch = triePr[ind].child[cl][cr];
triePr[ind].markedSub -= triePr[ch].markedSub;
insertPr(s,l+1,r-1,triePr[ind].child[cl][cr]);
triePr[ind].markedSub += triePr[ch].markedSub;
}
void insertPr(string& s){
insertPr(s, 0, s.size()-1);
}
void insertSing(string& s, int i, vector<TrieNode>& trie, int ind = 0){
if(i == s.size()) {
triePr[ind].marked++;
triePr[ind].markedSub++;
return;
}
int ci = conv(s[i]);
if(trie[ind].child[ci] == -1){
trie[ind].child[ci] = trie.size();
trie.push_back(TrieNode());
}
int ch = trie[ind].child[ci];
trie[ind].markedSub -= trie[ch].markedSub;
insertPr(s,i+1,trie[ind].child[ci]);
trie[ind].markedSub += trie[ch].markedSub;
}
int trav(string& p, string& s, int i, int indP){
if(indP == -1) return 0;
if(i == max(p.size(),s.size())){
return triePr[indP].markedSub;
}
if(i < p.size() && i < s.size()){
int cl = conv(p[i]);
int cr = conv(s[i]);
int c = triePr[indP].child[cl][cr];
if(c == -1) return 0;
return trav(p,s,i+1,c);
}
if(i < p.size() && i >= s.size()){
int cl = conv(p[i]);
int r1 = trav(p,s,i+1,triePr[indP].child[cl][0]);
int r2 = trav(p,s,i+1,triePr[indP].child[cl][1]);
int r3 = trav(p,s,i+1,triePr[indP].child[cl][2]);
int r4 = trav(p,s,i+1,triePr[indP].child[cl][3]);
return r1+r2+r3+r4;
}
if(i >= p.size() && i < s.size()){
int cr = conv(s[i]);
int r1 = trav(p,s,i+1,triePr[indP].child[0][cr]);
int r2 = trav(p,s,i+1,triePr[indP].child[1][cr]);
int r3 = trav(p,s,i+1,triePr[indP].child[2][cr]);
int r4 = trav(p,s,i+1,triePr[indP].child[3][cr]);
return r1+r2+r3+r4;
}
// what the flip?
assert(false);
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m;
for(int i = 0; i < n; i++){
string s;
cin >> s;
insertPr(s);
insertSing(s, 0, trieP, 0);
reverse(s.begin(),s.end());
insertSing(s, 0, trieS, 0);
}
for(int i =0; i < m; i++){
string p,s;
cin >> p >> s;
reverse(s.begin(),s.end());
cout << trav(p,s,0,0) << "\n";
}
}
