#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int trie[2002002][4], cnt;
vector<int> id[2002002];
int ic, in[2002002], out[2002002], rc, r[2002002], rin[2002002];

int n, m, C[256], ans[2002002], t[2002002];
string s[2002002], L[2002002], R[2002002];
vector<int> q[2002002];

void dfs(int u) {
    in[u] = rc+1;
    for(auto x : id[u]) r[++rc] = x;
    for(int i=0;i<4;i++) if(trie[u][i]) dfs(trie[u][i]);
    out[u] = rc;
}

void dfs2(int u) {
    in[u] = ++ic;
    for(int i=0;i<4;i++) if(trie[u][i]) dfs2(trie[u][i]);
    out[u] = ic;
}

int find(int b) {
    int re = 0;
    while(b) re += t[b], b -= b & -b;
    return re;
}

int main() {
    C['A'] = 0, C['C'] = 1, C['G'] = 2, C['U'] = 3;
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        cin >> s[i];
        int u = 0;
        for(auto c : s[i]) {
            c = C[c];
            if(!trie[u][c]) trie[u][c] = ++cnt;
            u = trie[u][c];
        }
        id[u].push_back(i);
    }

    dfs(0);

    for(int i=1;i<=m;i++) {
        cin >> L[i] >> R[i];

        int u = 0;
        for(auto c : L[i]) {
            c = C[c];
            if(!trie[u][c]) { u = -1; break; }
            u = trie[u][c];
        }

        if(u != -1) {
            q[in[u]-1].push_back(-i);
            q[out[u]].push_back(i);
        }
    }


    cnt = 0;
    memset(trie, 0, sizeof trie);
    for(int i=1;i<=n;i++) {
        reverse(s[i].begin(), s[i].end());
        int u = 0;
        for(auto c : s[i]) {
            c = C[c];
            if(!trie[u][c]) trie[u][c] = ++cnt;
            u = trie[u][c];
        }
        rin[i] = u;
    }

    ic = 0;
    dfs2(0);


    for(int i=1;i<=n;i++) {
        int u = in[rin[r[i]]];
        for(int b=u;b<=ic;b+=b&-b) t[b]++;

        for(auto x : q[i]) {
            auto &S = R[abs(x)];
            reverse(S.begin(), S.end());
            int u = 0;
            for(auto c : S) {
                c = C[c];
                if(!trie[u][c]) { u = -1; break; }
                u = trie[u][c];
            }
            if(u != -1) ans[abs(x)] += (x > 0 ? 1 : -1) * (find(out[u]) - find(in[u]-1));
        }
    }


    for(int i=1;i<=m;i++) cout << ans[i] << "\n";
}