#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
int code(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'U') return 2;
if(c == 'C') return 3;
assert(false);
}
struct Trie{
struct Node{
int next[4];
Node(){
memset(next, -1, sizeof(next));
}
};
vector<Node> nd;
Trie() { nd.emplace_back(); }
int size(){ return (int)nd.size(); }
void add(const string& s){
int u = 0;
for(auto ch : s){
int c = code(ch);
if(nd[u].next[c] == -1){
nd[u].next[c] = size();
nd.emplace_back();
}
u = nd[u].next[c];
}
}
int timer_dfs;
vector<int> tin, tout;
void dfsTree(int u){
tin[u] = ++timer_dfs;
for(int i = 0; i < 4; ++i){
if(nd[u].next[i] != -1){
dfsTree(nd[u].next[i]);
}
}
tout[u] = timer_dfs;
}
void construct_tree(){
timer_dfs = 0;
tin.resize(size());
tout.resize(size());
dfsTree(0);
assert(timer_dfs == size());
}
pair<int, int> get_subtree(int u){
assert(u < size());
return make_pair(tin[u], tout[u]);
}
int get(const string& s){
int u = 0;
for(auto ch : s){
int c = code(ch);
if(nd[u].next[c] == -1) return -1;
u = nd[u].next[c];
}
return u;
}
};
struct Fenwick{
vector<int> bit;
Fenwick(int n) : bit(n + 1, 0) {}
void update(int id, int val){
for(; id < (int)bit.size(); id += id & (-id)) bit[id] += val;
}
int query(int l, int r){
int sum = 0;
--l;
// cout << l << ' ' << r << '\n';
for(; l > 0; l -= l & (-l)) sum -= bit[l];
for(; r > 0; r -= r & (-r)) sum += bit[r];
return sum;
}
};
int main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
// if(fopen("task.inp", "r")){
// freopen("task.inp", "r", stdin);
// freopen("task.out", "w", stdout);
// }
int N, Q;
cin >> N >> Q;
vector<string> S(N);
Trie prefix_trie, suffix_trie;
for(int i = 0; i < N; ++i){
cin >> S[i];
prefix_trie.add(S[i]);
reverse(S[i].begin(), S[i].end());
suffix_trie.add(S[i]);
}
prefix_trie.construct_tree();
suffix_trie.construct_tree();
struct event{
int x, type, l, r, id;
bool operator < (const event& o){
return (x == o.x ? type < o.type : x < o.x);
}
};
vector<event> events;
for(int i = 0; i < N; ++i){
reverse(S[i].begin(), S[i].end());
int x = prefix_trie.get(S[i]);
reverse(S[i].begin(), S[i].end());
int y = suffix_trie.get(S[i]);
events.push_back({prefix_trie.tin[x], -1, suffix_trie.tin[y], suffix_trie.tin[y], i});
}
vector<int> ans(Q);
for(int i = 0; i < Q; ++i){
string p, q;
cin >> p >> q; reverse(q.begin(), q.end());
int i1 = prefix_trie.get(p), i2 = suffix_trie.get(q);
if(i1 == -1 || i2 == -1){
ans[i] = 0;
continue;
}
int l1, r1, l2, r2;
tie(l1, r1) = prefix_trie.get_subtree(i1);
tie(l2, r2) = suffix_trie.get_subtree(i2);
events.push_back({l1 - 1, 0, l2, r2, i});
events.push_back({r1, 1, l2, r2, i});
}
sort(events.begin(), events.end());
Fenwick ft(suffix_trie.size());
for(auto e : events){
if(e.type == -1){
ft.update(e.l, +1);
}
else{
if(e.type == 0) ans[e.id] -= ft.query(e.l, e.r);
else ans[e.id] += ft.query(e.l, e.r);
}
}
for(int i = 0; i < Q; ++i) cout << ans[i] << '\n';
return 0;
}
