#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>
#define N 100100
#define frm std::pair<std::string,int>
#define qry std::pair<int,std::pair<std::string,std::string>>
#define evt std::pair<int,std::pair<int,int>>
#define left(i) (i<<1)
#define right(i) ((i<<1)+1)
char str[N];
char strr[N];
std::vector<frm> inpp;
std::vector<frm> inps;
std::vector<qry> mp;
std::vector<evt> et;
std::vector<int> sol[N];
std::set<int> stt;
int pidx[N];
int n,m;
typedef struct trr{
int val;
int lz;
}trr;
trr seg[N*4];
void prop(int idx, int l, int r){
if(seg[idx].lz){
if(l != r-1){
seg[left(idx)].lz += seg[idx].lz;
seg[right(idx)].lz += seg[idx].lz;
};
seg[idx].val += seg[idx].lz;
seg[idx].lz = 0;
};
};
void update(int idx, int l, int r, int a, int b){
if(l >= r)return;
if(l >= b || a >= r)return;
if(a <= l && r <= b){
//printf("upd: %d %d %d\n",l,r,idx);
seg[idx].lz += 1;
}else{
int m = (l + r)>>1;
update(left(idx),l,m,a,b);
update(right(idx),m,r,a,b);
};
};
int qurry(int idx, int l, int r, int x){
prop(idx,l,r);
if(l == r-1){
//printf("qu: %d %d %d %d\n",l,r,seg[idx].lz,idx);
return seg[idx].val;
}else{
int m = (l + r)>>1;
if(m > x){
return qurry(left(idx),l,m,x);
}else{
return qurry(right(idx),m,r,x);
};
};
};
int cmp(frm a, frm b){
int ln;
int s11 = a.first.size();
int s12 = b.first.size();
ln = std::min(s11,s12);
for(int i = 0;i<ln;i++){
if(a.first[i] != b.first[i])return a.first[i] < b.first[i];
};
if(s12 > s11 && b.second == -1)return 1;
return 0;
};
int main(void){
scanf("%d %d",&n,&m);
std::string ss1;
std::string ss2;
for(int i = 0;i<n;i++){
scanf("%s",str);
ss1 = std::string(str);
inpp.push_back({ss1,i});
ss2 = std::string(ss1);
std::reverse(ss2.begin(),ss2.end());
inps.push_back({ss2,i});
};
std::sort(inpp.begin(),inpp.end(),std::less<frm>());
for(int i = 0;i<inpp.size();i++){
inps[inpp[i].second].second = i;
inpp[i].second = i;
};
std::sort(inps.begin(),inps.end(),std::less<frm>());
//printf("%d\n",inps.size());
for(int i = 0;i<inps.size();i++){
//printf("%d %s\n",inpp[i].second,inpp[i].first.c_str());
//printf("%d %s\n",inps[i].second,inps[i].first.c_str());
frm akt = inps[i];
pidx[akt.second] = i;
};
for(int i = 0;i<m;i++){
scanf("%s",str);
scanf("%s",strr);
ss1 = std::string(str);
ss2 = std::string(strr);
std::reverse(ss2.begin(),ss2.end());
auto pp = std::equal_range(inpp.begin(),inpp.end(),frm(ss1,-1),cmp);
auto ss = std::equal_range(inps.begin(),inps.end(),frm(ss2,-1),cmp);
int p1 = pp.first - inpp.begin();
int p2 = pp.second - inpp.begin();
int s1 = ss.first - inps.begin();
int s2 = ss.second - inps.begin();
//printf("%d %d %d %d\n",p1,p2,s1,s2);
et.push_back({p1,{s1,i}});
et.push_back({p1,{s2,i}});
et.push_back({p2,{s1,i}});
et.push_back({p2,{s2,i}});
};
std::sort(et.begin(),et.end(),std::less<evt>());
int idx = 0;
/*
puts("");
for(auto j: et){
printf("%d %d %d\n",j.first,j.second.first,j.second.second);
};
*/
/*
for(int i = 0;i<n;i++){
printf("pidx: %d\n",pidx[i]);
};
puts("");
*/
while(et[idx].first == 0){
sol[et[idx].second.second].push_back(0);
idx++;
};
for(int i = 1;i<=n;i++){
update(1,0,n,pidx[i-1],n);
while(idx < et.size() && et[idx].first == i){
//printf("%d %d %d %d\n",et[idx].first,et[idx].second.first,et[idx].second.second,idx);
int tmp = 0;
if(et[idx].second.first > 0){
tmp = qurry(1,0,n,et[idx].second.first-1);
//printf("tmp: %d\n",tmp);
};
sol[et[idx].second.second].push_back(tmp);
idx++;
};
};
for(int i = 0;i<m;i++){
int erg = 0;
if(sol[i].size()){
for(int j = 1;j<sol[i].size()-1;j++){
erg -= sol[i][j];
};
erg += sol[i][sol[i].size()-1] + sol[i][0];
};
printf("%d\n",erg);
};
return 0;
};
