/* Bismillahir Rahmanir Rahim */
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int M = 2000005;
int mp[M], from[M];
struct TRIE{
map <char, int> trie[M];
int in[M], out[M], cnt[M];
int idx, t;
void init(){
memset(cnt, 0, sizeof(cnt));
idx = 1;
t = 0;
}
int insert(string str, int ot){
int cur = 1;
for(auto c : str){
if(trie[cur].count(c) == 0) trie[cur][c] = ++idx;
cur = trie[cur][c];
}
from[cur] = ot;
++cnt[cur];
return cur;
}
int query(string str){
int cur = 1;
for(auto c : str){
if(trie[cur].count(c) == 0) return -1;
cur = trie[cur][c];
}
return cur;
}
void dfs(int at){
in[at] = ++t;
mp[t] = at;
for(auto c : {'A', 'C', 'G', 'U'}){
if(trie[at].count(c)){
dfs(trie[at][c]);
}
}
out[at] = t;
}
};
int n, m, k;
int nn, mm;
string rna[N];
TRIE t1, t2;
int id1[N], id2[N];
int root[M];
int lf[19 * M], rf[19 * M];
int sum[19 * M];
int idx;
int update(int b, int e, int node, int pos, int val){
int cur = ++idx;
sum[cur] = sum[node] + val;
if(b == e) return cur;
int mid = (b + e) / 2;
lf[cur] = lf[node];
rf[cur] = rf[node];
if(pos <= mid) lf[cur] = update(b, mid, lf[node], pos, val);
else rf[cur] = update(mid + 1, e, rf[node], pos, val);
return cur;
}
int get(int b, int e, int node, int x, int y){
if(y < b || e < x || node == 0) return 0;
if(b >= x && e <= y) return sum[node];
int mid = (b + e) / 2;
return get(b, mid, lf[node], x, y) + get(mid + 1, e, rf[node], x, y);
}
void init(){
t1.init();
for(int i = 1; i <= n; ++i){
id1[i] = t1.insert(rna[i], 0);
}
t1.dfs(1);
nn = t1.idx;
for(int i = 1; i <= n; ++i) reverse(rna[i].begin(), rna[i].end());
for(int i = 1; i <= n; ++i){
id2[i] = t2.insert(rna[i], t1.in[ id1[i] ]);
}
t2.dfs(1);
mm = t2.idx;
for(int i = 1; i <= mm; ++i){
int at = mp[i];
if(from[at] == 0) root[i] = root[i-1];
else{
root[i] = update(1, nn, root[i-1], from[at], t2.cnt[at]);
}
}
}
int query(string p, string q){
int a = t1.query(p);
int b = t2.query(q);
if(a == -1 || b == -1) return 0;
int aa = get(1, nn, root[ t2.out[b] ], t1.in[a], t1.out[a]);
int bb = get(1, nn, root[ t2.in[b] - 1 ], t1.in[a], t1.out[a]);
return aa - bb;
}
int main(){
ios_base::sync_with_stdio(false);
t1.init();
t2.init();
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> rna[i];
}
init();
string p, q;
for(int i = 1; i <= m; ++i){
cin >> p >> q;
reverse(q.begin(), q.end());
cout << query(p, q) << '\n';
}
return 0;
}
