#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int MAXN = 2e6+5;
int N,M;
int ans[MAXN];
vector<pair<int,int>> pts;
vector<array<int,4>> queries;
int toval(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'U') return 2;
if(c == 'C') return 3;
}
struct Trie{
int trie[MAXN][4],nodes;
int st[MAXN],num[MAXN]; //size and dfs order
int t;
int ins(string s){
int pos = 0;
for(int i = 0;i<s.size();++i){
int c = toval(s[i]);
if(!trie[pos][c]) trie[pos][c] = ++nodes;
pos = trie[pos][c];
}
return pos;
}
int finden(string s){
int pos = 0;
for(int i = 0;i<s.size();++i){
int c = toval(s[i]);
if(!trie[pos][c]) return -1;
pos = trie[pos][c];
}
return pos;
}
void dfs(int u){
num[u] = t++;
st[u] = 1;
for(int i = 0;i<=3;++i){
if(trie[u][i]){
dfs(trie[u][i]);
st[u] += st[trie[u][i]];
}
}
}
}pref, suf;
struct BIT{
int tree[MAXN];
void upd(int pos, int val){
++pos;
for(;pos < MAXN;pos += (pos&(-pos))){
tree[pos] += val;
}
}
int query(int pos){
++pos; int ret = 0;
while(pos > 0){
ret += tree[pos];
pos -= (pos&(-pos));
}
return ret;
}
}bit;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for(int i = 1;i<=N;++i){
string s; cin >> s;
int ind1 = pref.ins(s);
reverse(s.begin(),s.end());
int ind2 = suf.ins(s);
pts.push_back({ind1,ind2});
}
pref.t = suf.t = 0;
pref.dfs(0); suf.dfs(0);
for(int i = 0;i<pts.size();++i){
pts[i].ff = pref.num[pts[i].ff];
pts[i].ss = suf.num[pts[i].ss];
}
for(int i = 1;i<=M;++i){
string pref1, suf1; cin >> pref1 >> suf1;
reverse(suf1.begin(),suf1.end());
int u = pref.finden(pref1), v = suf.finden(suf1);
if(u == -1 || v == -1) ans[i] = 0;
else{
int pref2 = pref.num[u], suf2 = suf.num[v];
int szp = pref.st[u], szs = suf.st[v];
queries.push_back({pref2-1,suf2-1,i,1});
queries.push_back({pref2-1,suf2+suf.st[v]-1,i,-1});
queries.push_back({pref2+pref.st[u]-1,suf2-1,i,-1});
queries.push_back({pref2+pref.st[u]-1,suf2+suf.st[v]-1,i,1});
}
}
sort(pts.begin(),pts.end()); sort(queries.begin(),queries.end());
int P = pts.size(), Q = queries.size();
int pi = 0, qi = 0, nodes = pref.nodes;
//cout << P << " " << Q << "\n";
for(int i = 0;i<=nodes;++i){
while(pi < P){
int x = pts[pi].ff, y = pts[pi].ss;
if(x != i) break;
bit.upd(y,1);
++pi;
}
while(qi < Q){
int x = queries[qi][0], y = queries[qi][1], ind = queries[qi][2], w = queries[qi][3];
if(x != i) break;
int tmp = bit.query(y);
ans[ind] += w*tmp;
++qi;
}
}
for(int i = 1;i<=M;++i){
cout << ans[i] << "\n";
}
return 0;
}
