#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 2e6 + 5;
struct TRIE{
int tree[N][4];
int last, tin[N], tout[N], t;
int get(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
return 3;
}
int add(string& s){
int cur = 0;
for(int i=0;i<(int)s.size();i++){
int x = get(s[i]);
if(tree[cur][x]) cur = tree[cur][x];
else tree[cur][x] = ++last, cur = last;
} return cur;
}
void dfs(int u = 0){
tin[u] = ++t;
for(int k=0;k<4;k++){
if(tree[u][k]) dfs(tree[u][k]);
} tout[u] = t;
}
}tree;
struct BIT{
int tree[N];
void add(int i, int v){
for(;i<N;i+=(i&-i)) tree[i] += v;
}
int get(int i){
int rr = 0;
for(;i>0;i-=(i&-i)) rr += tree[i];
return rr;
}
int get(int l, int r){
return get(r) - get(l-1);
}
}bit;
vector<int> in[N], out[N], pp[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
vector<string> s(n), r(n), p(m), q(m);
for(int i=0;i<n;i++){
cin>>s[i];
r[i] = s[i];
reverse(r[i].begin(), r[i].end());
}
for(int i=0;i<m;i++){
cin>>p[i]>>q[i];
reverse(q[i].begin(), q[i].end());
}
vector<ar<int, 2>> t(n);
vector<ar<int, 2>> a(m), b(m);
{
tree.last = tree.t = 0;
vector<int> v(n), u(m);
for(int i=0;i<n;i++) v[i] = tree.add(s[i]);
for(int i=0;i<m;i++) u[i] = tree.add(p[i]);
tree.dfs();
for(int i=0;i<n;i++){
t[i][0] = tree.tin[v[i]];
}
for(int i=0;i<m;i++){
a[i][0] = tree.tin[u[i]];
a[i][1] = tree.tout[u[i]];
}
memset(tree.tree, 0, sizeof tree.tree);
}
{
tree.last = tree.t = 0;
vector<int> v(n), u(m);
for(int i=0;i<n;i++) v[i] = tree.add(r[i]);
for(int i=0;i<m;i++) u[i] = tree.add(q[i]);
tree.dfs();
for(int i=0;i<n;i++){
t[i][1] = tree.tin[v[i]];
}
for(int i=0;i<m;i++){
b[i][0] = tree.tin[u[i]];
b[i][1] = tree.tout[u[i]];
}
memset(tree.tree, 0, sizeof tree.tree);
}
//~ for(int i=0;i<n;i++) cout<<t[i][0]<<" "<<t[i][1]<<"\n";
//~ for(int i=0;i<m;i++){
//~ cout<<a[i][0]<<" "<<a[i][1]<<" \n"<<b[i][0]<<" "<<b[i][1]<<"\n\n";
//~ }
vector<int> res(m);
for(int i=0;i<m;i++){
in[a[i][0]].push_back(i);
out[a[i][1]].push_back(i);
} for(int i=0;i<n;i++){
pp[t[i][0]].push_back(t[i][1]);
}
for(int i=0;i<N;i++){
for(auto j : in[i]){
res[j] -= bit.get(b[j][0], b[j][1]);
}
for(auto j : pp[i]){
bit.add(j, 1);
}
for(auto j : out[i]){
res[j] += bit.get(b[j][0], b[j][1]);
}
}
for(int i=0;i<m;i++){
cout<<res[i]<<"\n";
}
}
