#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
const int maxl=2000005, mxn=100005;
vector<array<int,4>> to1, to2;
vector<int> l1, r1,l2, r2, pos1, pos2, base;
vector<vector<int>> sm1(maxl), sm2(maxl);
void init(){
to1.resize(maxl);
to2.resize(maxl);
l1.resize(maxl);
l2.resize(maxl);
r1.resize(maxl);
r2.resize(maxl);
pos1.resize(mxn);
pos2.resize(mxn);
base.resize(mxn);
}
int fw[100005];
void upd(int x, int v){
if(x<=0)return;
while(x<=mxn){
fw[x]+=v;
x+=(x&(-x));
}
}
int qry(int x){
//~ printf("qry %lld\n", x);
//~ fflush(stdout);
int ret=0;
while(x>0){
ret+=fw[x];
x-=(x&(-x));
}
return ret;
}
int nw1=1, nw2=1;
signed main(){
init();
int n, m;cin>>n>>m;
auto co=[&](char c) -> int {
if(c=='A')return 0;
else if(c=='U')return 1;
else if(c=='G')return 2;
else return 3;
};
for(int i=0;i<n;i++){
string s;cin>>s;
//~ cout<<"string " << s<<endl;
int cur=0;
int sz=s.size();
for(int i=0;i<sz;i++){
int nxt=co(s[i]);
if(to1[cur][nxt]!=0)cur=to1[cur][nxt];
else {
to1[cur][nxt]=nw1;
cur=nw1;
nw1++;
}
}
sm1[cur].push_back(i);
cur=0;
for(int i=sz-1;i>=0;i--){
int nxt=co(s[i]);
if(to2[cur][nxt]!=0){
cur=to2[cur][nxt];
}
else {
to2[cur][nxt]=nw2;
cur=nw2;
nw2++;
}
}
sm2[cur].push_back(i);
}
int t=1;
auto dfs = [&](auto&& dfs, int x,
const vector<array<int,4>>& to,
vector<int>& l, vector<int>& r,
vector<vector<int>>& sm, vector<int> & pos) -> void {
l[x]=t-1;
for(auto it : sm[x]){
pos[it]=t;
t++;
}
for(int i=0;i<4;i++){
if(to[x][i]!=0){
dfs(dfs, to[x][i], to,l,r,sm,pos);
}
}
r[x]=t-1;
//~ printf("at %lld, l is %lld, r is %lld\n", x, l[x], r[x]);
};
dfs(dfs, 0, to1,l1,r1, sm1, pos1);
t=1;
//~ printf("dfs2 now. \n");
dfs(dfs, 0, to2,l2,r2, sm2, pos2);
vector<array<array<int,2>, 2>> qr(m);
vector<int> ans(m, 0);
vector<vector<pair<int,int>>> todo(n+1);
for(int i=0;i<m;i++){
string a,b;cin>>a>>b;
int cur=0, done=0;
for(auto c : a){
int nxt=co(c);
if(to1[cur][nxt]!=0)cur=to1[cur][nxt];
else {
qr[i][0][0]=-1;
qr[i][0][1]=-1;
done=1;
}
}
if (!done) {
qr[i][0][0]=l1[cur], qr[i][0][1]=r1[cur];
//~ printf("qind %lld l1 %lld r1 %lld\n", i,qr[i][0][0], qr[i][0][1]);
}
cur=0, done=0;
for(int i=(int)b.size()-1;i>=0;i--){
int nxt=co(b[i]);
if(to2[cur][nxt]!=0){
cur=to2[cur][nxt];
}
else {
qr[i][1][0]=-1;
qr[i][1][1]=-1;
done=1;
}
}
if(!done) {
qr[i][1][0]=l2[cur], qr[i][1][1]=r2[cur];
todo[l2[cur]].push_back({i, 0});
todo[r2[cur]].push_back({i, 1});
}
//~ printf("query index %lld, 1range %lld to %lld, 2range %lld to %lld\n", i, qr[i][0][0], qr[i][0][1], qr[i][1][0],qr[i][1][1]);
}
for(int i=0;i<n;i++){
//~ printf("string index %lld, pos1 %lld, pos2 %lld\n", i,pos1[i], pos2[i]);
base[pos2[i]]=pos1[i];
}
//~ for(int i=1;i<=n;i++){
//~ printf("base %lld = %lld \n", i, base[i]);
//~ }
//~ return 0;
for(int i=1;i<=n;i++){
//~ printf("upd %lld\n", pos1[i]);
//~ fflush(stdout);
//~ cout<<endl<<i<<endl;
upd(base[i], 1);
for(auto [qind, type] : todo[i]){
//~ printf("qind %lld, type %lld, r %lld, l %lld, up %lld , down %lld\n", qind, type,qr[qind][0][1],qr[qind][0][0], qry(qr[qind][0][1]), qry(qr[qind][0][0]));
int res=qry(qr[qind][0][1]) - qry(qr[qind][0][0]);
if(type==0)ans[qind]-=res;
else ans[qind]+=res;
}
}
for(int i=0;i<m;i++){
cout<<ans[i]<<"\n";
}
}
