/* Bismillahir Rahmanir Rahim */
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int M = 2000005;
int mp[M], from[M];
int cc[N];
struct TRIE{
int trie[M][4];
int in[M], out[M], cnt[M];
int idx, t;
void init(){
memset(cnt, 0, sizeof(cnt));
memset(trie, 0, sizeof(trie));
idx = 1;
t = 0;
}
int insert(string str, int ot){
int cur = 1;
for(auto u : str){
int c = cc[u];
if(trie[cur][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 u : str){
int c = cc[u];
if(trie[cur][c] == 0) return -1;
cur = trie[cur][c];
}
return cur;
}
void dfs(int at){
in[at] = ++t;
mp[t] = at;
for(int c = 0; c <= 3; ++c){
if(trie[at][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[20 * M], rf[20 * M];
int sum[20 * 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(){
cc['A'] = 0;
cc['C'] = 1;
cc['G'] = 2;
cc['U'] = 3;
t1.init();
t2.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);
reverse(q.begin(), q.end());
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;
}
char str[N], p[N], q[N];
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i){
scanf("%s", str);
rna[i] = (string)(str);
}
init();
for(int i = 1; i <= m; ++i){
scanf("%s", p);
scanf("%s", q);
cout << query(p, q) << '\n';
}
return 0;
}
