#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, leaf, qrs;
    int siz{1};
    trie(int x) {
        siz = 1;
        nxt.assign(1, vector<int>(4, -1));
        leaf.assign(1, {});
        qrs.assign(1, {});
    }
    void add_word(vector<int>& s, int wi) {
        int v = 0;
        for (int i = 0; i < s.size(); i++) {
            if (nxt[v][s[i]] == -1) {
                nxt[v][s[i]] = siz++;
                nxt.pb(vector<int>(4, -1));
                leaf.pb({});
                qrs.pb({});
            }
            v = nxt[v][s[i]];
        }
        leaf[v].pb(wi);
    }

    int find_word(vector<int> &s) {
        int v = 0;
        for (int i = 0; i < s.size(); i++) {
            if (nxt[v][s[i]] == -1) return -1;
            v = nxt[v][s[i]];
        }
        return v;
    }
};

struct fenwick {
    int n;
    unordered_map<int, int> t;
    fenwick() = default;
    fenwick(int n_) {
        n = n_;
    }

    void clear() {
        t.clear();
    }
 
    void upd(int p, int vl) {
        for (; p <= n; p = (p | (p + 1))) t[p] += vl;
    }
 
    int get(int p) {
        int sm = 0;
        for (; p > 0; p = (p & (p + 1)) - 1) sm += t[p];
        return sm;
    }
};

void solve() {
    int n, m; cin >> n >> m;
    trie tpref(1), tsuff(1);

    vector<char> alph = {'A', 'G', 'C', 'U'};

    auto tow = [&](string s) {
        vector<int> word(sz(s));
        for (int i = 0; i < sz(s); i++) {
            for (int j = 0; j < 4; j++) {
                if (alph[j] == s[i]) word[i] = j;
            }
        }
        return word;
    };

    vector<int> ans(m, 0);
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        vector<int> wrd;
        for (int j = 0; j < s.size(); j++) {
            for (int k = 0; k < 4; k++) {
                if (alph[k] == s[j]) wrd.pb(k);
            }
        }
        tpref.add_word(wrd, i);
        reverse(all(s));
        wrd = tow(s);
        tsuff.add_word(wrd, i);
    }

    for (int i = 0; i < m; i++) {
        string pr, sf; cin >> pr >> sf;
        vector<int> PR = tow(pr), SF = tow(sf);
        int vt = tpref.find_word(PR);
        if (vt == -1) {
            continue;
        }
        tpref.qrs[vt].pb(i);
        reverse(all(SF));
        vt = tsuff.find_word(SF);
        if (vt == -1) continue;
        tsuff.qrs[vt].pb(i);
    }
    vector<pair<int, int>> gs(m, {-1, -1});
    vector<int> vts, pos(n);
    auto dfs1 = [&](int v, auto&&self) -> void {
        for (int ind : tpref.qrs[v]) {
            gs[ind].first = sz(vts);
        }
        for (int ind : tpref.leaf[v]) {
            pos[ind] = sz(vts);
            vts.pb(ind);
        }
        for (int j = 0; j < 4; j++) {
            if (tpref.nxt[v][j] != -1) self(tpref.nxt[v][j], self);
        }
        for (int ind : tpref.qrs[v]) {
            gs[ind].second = sz(vts);
        }
    };
    dfs1(0, dfs1);

    vector<vector<int>> sub(sz(tsuff.nxt));
    vector<fenwick> fw(sz(tsuff.nxt));
    auto dfs2 = [&](int v, auto&&self) -> void {
        int sons = 0;
        for (int j = 0; j < 4; j++) {
            if (tsuff.nxt[v][j] != -1) {
                sons++; self(tsuff.nxt[v][j], self);
            }
        }
        if (!sons) {
            fw[v] = fenwick(n + 1);
            for (int vt : tsuff.leaf[v]) {
                sub[v].pb(vt);
                fw[v].upd(pos[vt] + 1, 1);
            }
            for (int ind : tsuff.qrs[v]) {
                if (gs[ind].first != -1) {
                    ans[ind] = fw[v].get(gs[ind].second + 1) - fw[v].get(gs[ind].first);
                }
            }
            return;
        }
        int bs = -1;
        for (int j = 0; j < 4; j++) {
            if (tsuff.nxt[v][j] != -1 && (bs == -1 || sz(sub[bs]) < sz(sub[tsuff.nxt[v][j]]))) bs = tsuff.nxt[v][j];
        }
        swap(fw[bs], fw[v]);
        swap(sub[bs], sub[v]);
        for (int j = 0; j < 4; j++) {
            if (tsuff.nxt[v][j] != -1 && tsuff.nxt[v][j] != bs) {
                int vb = tsuff.nxt[v][j];
                for (int V : sub[vb]) {
                    sub[v].pb(V);
                    fw[v].upd(pos[V] + 1, 1);
                }
                fw[vb].clear();
                sub[vb].clear();
            }
        }
        for (int vt : tsuff.leaf[v]) {
            sub[v].pb(vt);
            fw[v].upd(pos[vt] + 1, 1);
        }
        for (int ind : tsuff.qrs[v]) {
            if (gs[ind].first != -1) {
                ans[ind] = fw[v].get(gs[ind].second) - fw[v].get(gs[ind].first);
            }
        }
    };
    dfs2(0, dfs2);
    for (int i = 0; i < m; i++) cout << ans[i] << '\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;
}