#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

struct trie {
    vector<vector<int>> nxt;
    vector<int> sub, leaf;
    int siz = 1;
    trie() {
        nxt.assign(1, vector<int>(4, 0));
        sub.assign(1, 0);
        leaf.assign(1, 0);
    }

    void clear() {
        nxt.clear();
    }

    void add(vector<int> &word) {
        int v = 0;
        for (int i = 0; i < sz(word); i++) {
            sub[v]++;
            if (nxt[v][word[i]] == 0) {
                nxt[v][word[i]] = siz++;
                nxt.pb(vector<int>(4, 0));
                sub.pb(0);
                leaf.pb(0);
            }
            v = nxt[v][word[i]];
        }
        sub[v]++;
        leaf[v]++;
    }

    int find(vector<int>&word) {
        int v = 0;
        for (int i = 0; i < sz(word); i++) {
            if (nxt[v][word[i]] == 0) return -1;
            v = nxt[v][word[i]];
        }
        return v;
    }

    int get(vector<int>& word) {
        int vt = find(word);
        return (vt == -1 ? 0 : sub[vt]);
    }
};

void solve() {
    int n, m; cin >> n >> m;
    trie T_pref;
    vector<char> ch = {'A', 'U', 'G', 'C'};

    auto conv = [&](string& s) {
        vector<int> cword(s.size());
        for (int j = 0; j < s.size(); j++) {
            for (int k = 0; k < 4; k++) {
                if (ch[k] == s[j]) cword[j] = k;
            }
        }
        return cword;
    };

    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        vector<int> cword = conv(s);
        T_pref.add(cword);
    }

    vector<vector<pair<vector<int>, int>>> Q(T_pref.siz);
    vector<int> ans(m);
    for (int i = 0; i < m; i++) {
        string pref, suff; cin >> pref >> suff;
        vector<int> pr = conv(pref), sf = conv(suff);
        reverse(all(sf));
        int vt = T_pref.find(pr);
        if (vt != -1) {
            Q[vt].pb({sf, i});
        }
    }
    vector<int> path;
    auto dfs = [&](int v, auto&&self) -> pair<trie, vector<vector<int>>> {
        int bs = -1;
        vector<int> sons, lett;
        for (int j = 0; j < 4; j++) {
            if (T_pref.nxt[v][j] != 0) {
                sons.pb(T_pref.nxt[v][j]);
                lett.pb(j);
                if (bs == -1 || T_pref.sub[bs] < T_pref.sub[sons.back()]) bs = sons.back();
            }
        }
        if (bs == -1) {
            trie Tcur;
            assert(T_pref.leaf[v]);
            vector<int> cw = path;
            reverse(all(cw));
            vector<vector<int>> sbtr;
            for (int j = 0; j < T_pref.leaf[v]; j++) {
                Tcur.add(cw);
                sbtr.pb(cw);
            }
            for (auto [SF, ind] : Q[v]) {
                ans[ind] = Tcur.get(SF);
            }
            return {Tcur, sbtr};
        }
        trie Tcur;
        vector<vector<int>> sbtr;
        int CIND = 0;
        for (auto &u : sons) {
            if (u == bs) {
                path.pb(lett[CIND]);
                auto result = self(u, self);
                path.pop_back();
                swap(Tcur,result.first);
                swap(sbtr,result.second);
            }
            CIND++;
        }
        CIND = 0;
        for (auto &u : sons) {
            if (u != bs) {
                 path.pb(lett[CIND]);
                auto result = self(u, self);
                path.pop_back();
                for (auto wrd : result.second) {
                    sbtr.pb(wrd);
                    Tcur.add(wrd);
                }
                result.first.clear(); result.second.clear();
            }
            CIND++;
        }
        if (T_pref.leaf[v]) {
            vector<int> cw = path;
            reverse(all(cw));
            for (int j = 0; j < T_pref.leaf[v]; j++) {
                Tcur.add(cw);
                sbtr.pb(cw);
            }
        }
        for (auto [SF, ind] : Q[v]) {
            ans[ind] = Tcur.get(SF);
        }
        return {Tcur, sbtr};
    };  
    dfs(0, dfs);
    for (auto &u : ans) cout << u << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}