#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define all(x) x.begin(), x.end()
#define TASK "RNA"
/// end of template ///
const int N = 1e5 + 15;
const int M = 2e6 + 26;
struct Query {
int x,b,t,xxx,id;
Query() {}
Query(int x, int b, int t, int xxx, int id) : x(x), b(b), t(t), xxx(xxx), id(id) {}
bool operator < (const Query &S) const {
return x<S.x;
}
};
char mp[26];
int numString,numQuery,ptr=1,bit[M*2],dp[N];
ii point[N];
vector<Query> v;
void add(int x, int val) {
// cout<<x<<'\n';
// return;
while (x<M*2) {
bit[x]+=val;
x+=x&-x;
}
}
int get(int x) {
int ans=0;
while (x>=1) {
ans+=bit[x];
x-=x&-x;
} return ans;
}
struct trie {
int tg,tr[M][4],st[M],en[M];
trie() {tg=1;}
int add(string s) {
int u=1;
for (char ch : s) {
int nxt=mp[ch-'A'];
if (tr[u][nxt]==0) tr[u][nxt]=++tg;
u=tr[u][nxt];
} return u;
}
void dfs(int u, int pa) {
st[u]=++tg;
for (int i=0; i<4; ++i) {
int v=tr[u][i];
if (v!=0) dfs(v,u);
}
en[u]=++tg;
}
void work() {
tg=0; dfs(1,-1);
}
} pre,suf;
void solve() {
mp['G'-'A']=0;
mp['U'-'A']=1;
mp['A'-'A']=2;
mp['C'-'A']=3;
cin>>numString>>numQuery;
for (int i=1; i<=numString; ++i) {
string s; cin>>s;
point[i].se=pre.add(s);
reverse(all(s));
point[i].fi=suf.add(s);
// cout<<point[i].fi<<' '<<point[i].se<<'\n';
} pre.work(); suf.work();
for (int i=1; i<=numString; ++i) point[i].se=pre.st[point[i].se],point[i].fi=suf.st[point[i].fi];
// for (int i=1; i<=numString; ++i) if (min(point[i].fi,point[i].se)==0) cout<<i<<' '<<point[i].fi<<' '<<point[i].se<<'\n';
for (int i=1; i<=numQuery; ++i) {
string s,t; cin>>s>>t; reverse(all(t));
int us=1;
bool is=1;
for (char ch : s) {
us=pre.tr[us][mp[ch-'A']];
if (us==0) {
is=0;
break;
}
}
int ut=1;
for (char ch : t) {
ut=suf.tr[ut][mp[ch-'A']];
if (ut==0) {
is=0;
break;
}
}
if (is==0) continue;
int b=pre.st[us],top=pre.en[us],l=suf.st[ut],r=suf.en[ut];
v.pb(Query(r,b,top,1,i));
v.pb(Query(l-1,b,top,-1,i));
}
sort(all(v));
sort(point+1,point+1+numString);
for (Query &cm : v) {
while (point[ptr].fi<=cm.x && ptr<=numString) add(point[ptr].se,1),++ptr;
dp[cm.id]+=cm.xxx*(get(cm.t)-get(cm.b-1));
}
for (int i=1; i<=numQuery; ++i) cout<<dp[i]<<'\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
int testcase=1;
// cin>>testcase;
while (testcase--)
solve();
return 0;
}
