#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MOD 1000000007
#define BASE 257
typedef long long int lld;
typedef pair<int,int> pii;
class FT{
int FT[2000000];
int N;
public:
void init(int n){
N=n;
for(int i=0;i<=N;i++)FT[i]=0;
}
void upd(int pos){
for(int i=pos;i<=N;i+=i&(-i)){
FT[i]++;
}
}
int query(int pos){
int ans=0;
for(int i=pos;i>0;i-=i&(-i)){
ans+=FT[i];
}return ans;
}
};
struct Trie{
struct Trie *child[26];
vector<int> end;
};
void insert(Trie *T,string s, int index){
Trie *S=T;
for(int i=0;i<s.length();i++){
int u=s[i]-'A';
if(!S->child[u]){
S->child[u]=new Trie();
for(int j=0;j<26;j++)S->child[u]->child[j]=NULL;
}
S=S->child[u];
}
S->end.push_back(index);
}
pair<int,int> Query1[1000000];
vector<int> EulerTour1;
pair<int,int> Query2[1000000];
vector<int> EulerTour2;
void DFS1(Trie *T){
sort(T->end.begin(),T->end.end());
for(int i=0;i<T->end.size();i++){
if(T->end[i]<=0){
Query1[-T->end[i]].first=EulerTour1.size();
}else EulerTour1.push_back(T->end[i]-1);
//cout<<T->end[i]<<" ";
}
//cout<<endl;
for(int i=0;i<26;i++){
if(T->child[i]){
DFS1(T->child[i]);
}
}
for(int i=0;i<T->end.size();i++){
if(T->end[i]<=0){
Query1[-T->end[i]].second=EulerTour1.size();
}
//cout<<T->end[i]<<" ";
}
}
void DFS2(Trie *T){
sort(T->end.begin(),T->end.end());
for(int i=0;i<T->end.size();i++){
if(T->end[i]<=0){
Query2[-T->end[i]].first=EulerTour2.size();
}else EulerTour2.push_back(T->end[i]-1);
//cout<<T->end[i]<<" ";
}
//cout<<endl;
for(int i=0;i<26;i++){
if(T->child[i]){
DFS2(T->child[i]);
}
}
for(int i=0;i<T->end.size();i++){
if(T->end[i]<=0){
Query2[-T->end[i]].second=EulerTour2.size();
}
//cout<<T->end[i]<<" ";
}
}
int main(){
int n,m;
cin>>n>>m;
string arr[n];
Trie *T=new Trie();
for(int i=0;i<n;i++){
cin>>arr[i];
insert(T,arr[i],i+1);
}
string Queries1[m];
string Queries2[m];
for(int i=0;i<m;i++){
cin>>Queries1[i]>>Queries2[i];
insert(T,Queries1[i],-i);
}
DFS1(T);
/*for(int i=0;i<n;i++){
cout<<EulerTour1[i]<<endl;
}
for(int i=0;i<m;i++){
cout<<Query1[i].first<<" "<<Query1[i].second<<endl;
}*/
T=new Trie();
for(int i=0;i<n;i++){
reverse(arr[i].begin(),arr[i].end());
insert(T,arr[i],i+1);
}
for(int i=0;i<m;i++){
reverse(Queries2[i].begin(),Queries2[i].end());
insert(T,Queries2[i],-i);
}
DFS2(T);
/*for(int i=0;i<m;i++){
cout<<Query2[i].first<<" "<<Query2[i].second<<endl;
}*/
pair<int,int> ET[n];
for(int i=0;i<n;i++){
ET[EulerTour1[i]].first=i;
ET[EulerTour2[i]].second=i;
}sort(ET,ET+n);
int answer[4*m];
vector<pair<pii,int> >Queries;
for(int i=0;i<m;i++){
Queries.push_back(pair<pii,int>(pii(Query1[i].first,Query2[i].first),4*i));
Queries.push_back(pair<pii,int>(pii(Query1[i].first,Query2[i].second),4*i+1));
Queries.push_back(pair<pii,int>(pii(Query1[i].second,Query2[i].first),4*i+2));
Queries.push_back(pair<pii,int>(pii(Query1[i].second,Query2[i].second),4*i+3));
}
sort(Queries.begin(),Queries.end());
int pnt=0;
FT *F=new FT();
F->init(n);
for(int i=0;i<4*m;i++){
while(pnt<Queries[i].first.first){
pnt++;
F->upd(ET[pnt-1].second+1);
}
answer[Queries[i].second]=F->query(Queries[i].first.second);
}
for(int i=0;i<m;i++){
cout<<answer[4*i]+answer[4*i+3]-answer[4*i+1]-answer[4*i+2]<<endl;
}
//cout<<'G'-'A'<<endl;
return 0;
}
