#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#define ALPHABET 4
#define MAXS 2000000
using namespace std;
struct node {
    int children[ALPHABET];
    vector <int> words;
    int min1,max1;
};
struct trie {
private:
    inline int get_code (char c) {
        if (c=='A') return 0;
        if (c=='C') return 1;
        if (c=='G') return 2;
        return 3;
    }

public:
    vector <node> nodes;
    trie () {
        nodes.push_back(node());
    }
    void add (string& w, int ind, bool type) {
        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().min1=1e9;
            }
            curr=nodes[curr].children[code];
            if (type==0) {
                nodes[curr].min1=min(nodes[curr].min1,ind);
                nodes[curr].max1=max(nodes[curr].max1,ind);
            }
            else nodes[curr].words.push_back(ind);
        }
    }

    int match (string& w) {
        int curr=0;
        for (auto c : w) {
            int code=get_code(c);
            if (nodes[curr].children[code]==0) return -1;
            curr=nodes[curr].children[code];
        }
        return curr;
    }
};
trie normal,reversed;

int bin_search (vector <int>& nums, int val) {
    int l=-1,r=nums.size();
    for (;;) {
        if (l==r-1) break;
        int mid=(l+r)/2;
        if (nums[mid]<=val) l=mid;
        else r=mid;
    }
    return l;
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q ;
    multiset <string> words;
    for (int i=0; i<n; i++) {
        string w;
        cin >> w ;
        words.insert(w);
    }
    int ind=0;
    for (auto w : words) {
        normal.add(w,ind,0);
        reverse(w.begin(),w.end());
        reversed.add(w,ind,1);
        ind++;
    }
    for (int i=0; i<q; i++) {
        string s,e;
        cin >> s >> e ;
        reverse(e.begin(),e.end());
        int pref=normal.match(s);
        if (pref==-1) {
            cout << 0 << "\n";
            continue;
        }
        int suff=reversed.match(e);
        if (suff==-1) {
            cout << 0 << "\n";
            continue;
        }
        cout << bin_search(reversed.nodes[suff].words,normal.nodes[pref].max1)-bin_search(reversed.nodes[suff].words,normal.nodes[pref].min1-1) << "\n";
    }
    return 0;
}
