#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;
vector <char> s[DIM];
char p[DIM],q[DIM],w[DIM],a[DIM];
int poz[DIM],lg[DIM];
int n,m,i,j,l,r,sol;
struct trie{
int l,r;
trie *f[27];
trie(){
l = INF, r = 0;
for (int i=0;i<26;i++)
f[i] = 0;
}
};
trie *rad1 = new trie;
struct trie2{
vector <int> v;
trie2 *f[27];
trie2(){
for (int i=0;i<26;i++)
f[i] = 0;
}
};
trie2 *rad2 = new trie2;
void add (trie *rad, char *s){
if (*s == NULL){
rad->l = min (rad->l,i);
rad->r = max (rad->r,i);
//rad->l = rad->r = i;
} else {
if (rad->f[*s-'A'] == 0)
rad->f[*s-'A'] = new trie;
add (rad->f[*s-'A'],s+1);
}
}
void dfs (trie *rad){
if (rad == NULL)
return;
for (int i=0;i<26;i++){
if (rad->f[i]){
dfs (rad->f[i]);
rad->l = min (rad->l,rad->f[i]->l);
rad->r = max (rad->r,rad->f[i]->r);
}
}
}
void dfs2 (trie2 *rad){
if (rad == NULL)
return;
sort (rad->v.begin(),rad->v.end());
for (int i=0;i<26;i++)
if (rad->f[i])
dfs2 (rad->f[i]);
}
void add2 (trie2 *rad, char *s){
rad->v.push_back(i);
if (*s == NULL){
return;
} else {
if (rad->f[*s-'A'] == NULL)
rad->f[*s-'A'] = new trie2;
add2 (rad->f[*s-'A'],s+1);
}
}
void query (trie *rad, char *s){
if (*s == NULL)
l = rad->l, r = rad->r;
else {
if (rad->f[*s-'A'] == NULL)
return;
query (rad->f[*s-'A'],s+1);
}
}
void query2 (trie2 *rad, char *s){
if (*s == NULL){
/// cate elemente din vectoru asta sunt intre l si r
for (int i=0;i<rad->v.size();i++)
if (rad->v[i] >= l && rad->v[i] <= r)
sol++;
return;
} else {
if (rad->f[*s-'A'] == NULL)
return;
query2 (rad->f[*s-'A'],s+1);
}
}
inline int cmp (int a, int b){
for (int i=0;i<min(lg[a],lg[b]);i++)
if (s[a][i] != s[b][i])
return s[a][i] < s[b][i];
return lg[a] < lg[b];
}
void copiere (char w[], vector<char> v){
for (int i=0;i<v.size();i++)
w[i] = v[i];
w[v.size()] = NULL;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m;
for (i=1;i<=n;i++){
cin>>a;
lg[i] = strlen(a);
for (j=0;j<lg[i];j++)
s[i].push_back(a[j]);
poz[i] = i;
}
sort (poz+1,poz+n+1,cmp);
for (i=1;i<=n;i++){
copiere (w,s[poz[i]]);
add (rad1,w);
}
dfs (rad1);
for (i=1;i<=n;i++){
reverse (s[poz[i]].begin(),s[poz[i]].end());
copiere (w,s[poz[i]]);
add2 (rad2,w);
}
dfs2 (rad2);
for (;m--;){
cin>>p>>q;
l = r = 0;
query(rad1,p);
if (!l){
cout<<"0\n";
continue;
}
reverse (q,q+strlen(q));
sol = 0;
query2 (rad2,q);
cout<<sol<<"\n";
}
return 0;
}
