#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#define ALPHABET 4+1
#define MAXN 100000
#define MAXQ 100000
#define MAX 100000
#define MAXS 2000000
using namespace std;
struct node {
    int children[ALPHABET];
    int fail,ok;
    vector <int> models;
    int cnt;
};
struct trie {
private:
    inline int get_code (char c) {
        if (c=='A') return 0;
        if (c=='C') return 1;
        if (c=='G') return 2;
        if (c=='U') return 3;
        return 4;
    }

public:
    vector <node> nodes;
    trie () {
        nodes.push_back(node());
        nodes.back().fail=nodes.back().ok=-1;
    }
    void add (string& w, int ind) {
        int curr=0;
        for (auto c : w) {
            int code=get_code(c);
            if (nodes[curr].children[code]==0) {
                nodes[curr].children[code]=nodes.size();
                nodes.push_back(node());
                nodes.back().fail=nodes.back().ok=0;
            }
            curr=nodes[curr].children[code];
        }
        nodes[curr].models.push_back(ind);
    }
    void Aho_Corasick () {
        queue <int> bfs;
        bfs.push(0);
        while (!bfs.empty()) {
            int parent=bfs.front();
            bfs.pop();
            for (int i=0; i<ALPHABET; i++) {
                int child=nodes[parent].children[i];
                if (child==0) continue;
                bfs.push(child);

                int curr=nodes[parent].fail;
                while (curr!=-1) {
                    if (nodes[curr].children[i]!=0) {
                        nodes[child].fail=nodes[curr].children[i];
                        break;
                    }
                    curr=nodes[curr].fail;
                }
                int f=nodes[child].fail;
                if (!nodes[f].models.empty()) nodes[child].ok=f;
                else nodes[child].ok=nodes[f].ok;
                //cout << child << " " << nodes[f].ok << endl ;
            }
        }
    }
    void find (string& text) {
        int curr=0;
        for (auto c : text) {
            int code=get_code(c);
            while (curr!=-1) {
                if (nodes[curr].children[code]!=0) {
                    curr=nodes[curr].children[code];
                    break;
                }
                curr=nodes[curr].fail;
            }
            if (curr==-1) curr=0;
            int tmp=curr;
            while (tmp>0) {
                nodes[tmp].cnt++;
                /*for (int ind : nodes[tmp].models) {
                    cout << ind+1 << " ";
                }*/
                tmp=nodes[tmp].ok;
            }
        }
    }
};
trie t;
string words[MAXN];
int ans[MAXQ];
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q ;
    for (int i=0; i<n; i++) {
        cin >> words[i] ;
    }
    for (int i=0; i<q; i++) {
        string s,e;
        cin >> s >> e ;
        e+="$"+s;
        t.add(e,i);
    }

    t.Aho_Corasick();
    for (int i=0; i<n; i++) {
        words[i]+="$"+words[i];
        //cout << i+1 << ": ";
        t.find(words[i]);
        //cout << endl ;
    }
    for (auto& node : t.nodes) {
        for (auto ind : node.models) {
            ans[ind]+=node.cnt;
        }
    }

    for (int i=0; i<q; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}
