#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;
int f(char c){
if(c == 'A') return 0;
if(c == 'C') return 1;
if(c == 'G') return 2;
return 3;
}
struct trie_t{
vector<array<int, 4>>nodes;
vector<vector<int>>v;
int n, m;
vector<int>x, a, b;
trie_t (int c = 0, int d = 0) : n(c), m(d), x(c), a(d), b(d), nodes(1, {-1, -1, -1, -1}), v(1) {}
int timer = 0;
void add(string s, int id){
int cur = 0;
for(char c : s){
int e = f(c);
if(nodes[cur][e] == -1){
nodes[cur][e] = (int)nodes.size();
nodes.push_back({-1, -1, -1, -1});
v.push_back({});
}
cur = nodes[cur][e];
}
v[cur].push_back(id);
}
void dfs(int cur){
for(int u : v[cur]){
if(u < m) a[u] = timer;
else x[u-m] = timer++;
}
for(int e=0;e<4;e++){
if(nodes[cur][e] == -1) continue;
dfs(nodes[cur][e]);
}
for(int u : v[cur]){
if(u < m) b[u] = timer - 1;
}
}
};
template<typename T> struct FT {
vector<T> s;
FT(int n) : s(n) {}
FT(const vector<T>& A) : s(int(A.size())) {
const int N = int(A.size());
for (int pos = 0; pos < N; ++pos) {
s[pos] += A[pos];
int nxt = (pos | (pos + 1));
if (nxt < N) s[nxt] += s[pos];
}
}
void update(int pos, T dif) { // a[pos] += dif
for (; pos < (int)s.size(); pos |= pos + 1) s[pos] += dif;
}
T query(int pos) { // sum of values in [0, pos)
T res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
int lower_bound(T sum) {// min pos st sum of [0, pos] >= sum
// Returns n if no sum is >= sum, or -1 if empty sum is.
if (sum <= 0) return -1;
int pos = 0;
for (int pw = 1 << 25; pw; pw >>= 1) {
if (pos + pw <= (int)s.size() && s[pos + pw-1] < sum)
pos += pw, sum -= s[pos-1];
}
return pos;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin>>n>>m;
trie_t trie(n, m), rtrie(n, m);
vector<string>s(n), t(n), p(m), q(m);
for(int i=0;i<n;i++){
cin>>s[i];
t[i] = s[i];
reverse(t[i].begin(), t[i].end());
}
for(int i=0;i<m;i++){
cin>>p[i]>>q[i];
reverse(q[i].begin(), q[i].end());
}
for(int i=0;i<m;i++){
trie.add(p[i], i);
rtrie.add(q[i], i);
}
for(int i=0;i<n;i++){
trie.add(s[i], m+i);
rtrie.add(t[i], m+i);
}
trie.dfs(0);
rtrie.dfs(0);
vector<int>x = trie.x, a = trie.a, b = trie.b;
vector<int>y = rtrie.x, c = rtrie.a, d = rtrie.b;
vector<array<int, 4>>v;
for(int i=0;i<m;i++){
}
for(int i=0;i<n;i++){
v.push_back({y[i], -1, x[i], 0});
}
for(int i=0;i<m;i++){
if(d[i] >= c[i] && b[i] >= a[i]){
v.push_back({d[i], a[i], b[i], i+1});
v.push_back({c[i] - 1, a[i], b[i], -i-1});
}
}
FT<int>seg(n);
sort(v.begin(), v.end());
vector<int>ans(m);
for(auto [_, j, k, id] : v){
if(j == -1){
seg.update(k, 1);
}
else{
int res = seg.query(k+1) - seg.query(j);
if(id > 0) ans[id-1] += res;
else ans[-id-1] -= res;
}
}
for(int i=0;i<m;i++) cout<<ans[i]<<"\n";
return 0;
}
/*
[ ]Leu o problema certo???
[ ]Ver se precisa de long long
[ ]Viu o limite dos fors (é n? é m?)
[ ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[ ]Testar sample
[ ]Testar casos de borda
[ ]1LL no 1LL << i
[ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/
