//pragma
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define YOU using
#define DONT namespace
#define SAY std

YOU DONT SAY;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define REPP(i,a,b,d) for(int i=a;i<=b;i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a;i>=b;i-=d)
#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) for(int i=0; i<a; i++)
#define FORD(i,a) for(int i=(int)a-1; i>=0; i--)

#define mp make_pair

#define pb push_back
#define F first
#define S second

const int OO = 1e9;
const ll INF = 1e18;

const int irand(int lo,int hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

const ll lrand(ll lo,ll hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

#define getc getchar
template<typename T>
T getnum(){
	int sign = 1;
	T ret = 0;
	char c;

	do{
		c = getc();
	}while(c == ' ' || c == '\n');
	if(c == '-')sign = -1;
	else ret = c-'0';
	while(1){
		c = getc();
		if(c < '0' || c > '9')break;
		ret = 10*ret + c-'0';
	}
	return sign * ret;
}

inline void ini(int& x){
	x = getnum<int>();
}

inline void scani(int& x){
	scanf("%d",&x);
}

//end of macro

struct node{
    node* next[26];
    int id;
    int l,r;
    vector<int>* qq;
    int size;
    node(){
        FOR(i,26)next[i] = NULL;
        id = -1;
        l = 0, r = 0;
        qq = NULL;
        size = 0;
    }
}head, headRev;

const int N = 1e5 + 5;

int n,m;
string strs[N];
int ids[N];

void add(string& str, int id){
    node* now = &head;
    FOR(i,str.size()){
        if(!now->next[str[i]-'a'])
            now->next[str[i]-'a'] = new node();
        now = now->next[str[i]-'a'];
    }
    now->id = id;
}

void addRev(string& str, int id){
    node* now = &headRev;
    FORD(i,str.size()){
        if(!now->next[str[i]-'a'])
            now->next[str[i]-'a'] = new node();
        now = now->next[str[i]-'a'];
    }
    now->id = id;
}

void clearAll(node* now){
    FOR(i,26){
        if(now->next[i]){
            clearAll(now->next[i]);
        }
    }
    if(now != &head)delete now;
}

int cntr = 0;
void dfs(node* now){
    int& left = now->l;
    int& right = now->r;
    left = OO, right = -OO;
    if(now->id > 0){
        ids[now->id] = ++cntr;
        left = right = cntr;
    }
    FOR(i,26){
        if(now->next[i]){
            dfs(now->next[i]);
            left = min(left, now->next[i]->l);
            right = max(right, now->next[i]->r);
        }
    }
}

string suf[N];
#define left sjdfkljsdf
#define right slkjdflksdj
int left[N], right[N];
int ans[N];

int bitt[N];
void update(int x, int v){
    REPP(i,x,N-5,i&-i){
        bitt[i] += v;
    }
}
int query(int x){
    int ret = 0;
    REVV(i,x,1,i&-i){
        ret += bitt[i];
    }
    return ret;
}
int query(int a, int b){
    return query(b) - query(a-1);
}

void initdfs(node* now){
    if(now->id > 0){
        now->size = 1;
    }
    FOR(i,26){
        if(now->next[i]){
            initdfs(now->next[i]);
            now->size += now->next[i]->size;
        }
    }
}
void add(node* now, node* exx, int v){
    if(now->id > 0){
        update(ids[now->id], v);
    }
    FOR(i,26){
        if(now->next[i] && now->next[i] != exx){
            add(now->next[i], exx, v);
        }
    }
}
int dsuontree(node* now, bool keep){
    node* big = NULL;
    FOR(i,26){
        if(now->next[i]){
            if(big == NULL || big->size < now->next[i]->size){
                big = now->next[i];
            }
        }
    }
    
    FOR(i,26){
        if(now->next[i] && now->next[i] != big){
            dsuontree(now->next[i], 0);
        }
    }
    
    if(big){
        dsuontree(big, 1);
    }
    
    add(now, big, 1);
    // query
    
    if(now->qq){
        auto qq = *(now->qq);
        FOR(i,qq.size()){
            int idq = qq[i];
//            printf("query %d\n",idq);
            
            int q = query(left[idq], right[idq]);
//            printf("intersect %d\n",q);
            ans[idq] = q;
        }
    }
    
    if(!keep){
        add(now, NULL, -1);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define endl '\n'
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);
    
    cin>>n>>m;
    REP(i,1,n){
        string str;
        cin>>str;
        add(str, i);
        strs[i] = str;
    }
    dfs(&head);
    
    REP(i,1,m){
        string pre;
        cin>>pre>>suf[i];
        bool fail = false;
        
        node* now = &head;
        FOR(j,pre.size()){
            if(!now->next[pre[j]-'a']){
                fail = true;
                break;
            }
            now = now->next[pre[j]-'a'];
        }
        if(fail)continue;
        left[i] = now->l;
        right[i] = now->r;
//        printf("%d %d\n",jumpto[i]->l, jumpto[i]->r);
    }
    
    clearAll(&head);
    
    REP(i,1,n){
        addRev(strs[i], i);
    }
    
    REP(i,1,m){
        if(left[i] == 0)continue;
        bool fail = false;
        node* now = &headRev;
        FORD(j,suf[i].size()){
//            printf("search %c\n",suf[i][j]);
            if(!now->next[suf[i][j]-'a']){
//                printf("not found!\n");
                fail = true;
                break;
            }
            now = now->next[suf[i][j]-'a'];
        }
        if(fail)continue;
        if(!now->qq)now->qq = new vector<int>();
        now->qq->pb(i);
//        printf("put\n");
    }
    
    initdfs(&headRev);
    dsuontree(&headRev, 0);
    
    REP(i,1,m){
        cout << ans[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 370648