#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=int;
#ifndef LOCAL
#define endl '\n'
#endif
struct Node{
map<pair<char,char>, lli> next;
lli cant=0;
};
vector<Node> trie;
lli currNode=0;
lli newNode(){
trie.pb(Node());
return currNode++;
}
void addword(string s, bool b,lli ind, lli pt){
for(lli i=ind; i<s.size(); ++i){
if(b){
if(trie[pt].next.find({s[i], 0})==trie[pt].next.end()){
trie[pt].next[{s[i], 0}]=newNode();
}
pt=trie[pt].next[{s[i],0}];
trie[pt].cant++;
}
else{
if(trie[pt].next.find({0,s[i]})==trie[pt].next.end()){
trie[pt].next[{0,s[i]}]=newNode();
}
pt=trie[pt].next[{0,s[i]}];
trie[pt].cant++;
}
}
}
void add(string s){
lli pt=0;
string r=s;
reverse(r.begin(), r.end());
for(lli i=0; i<s.size(); ++i){
deb(i);
trie[pt].cant++;
if(trie[pt].next.find({s[i], r[i]})==trie[pt].next.end()){
trie[pt].next[{s[i], r[i]}]=newNode();
}
addword(s, 1, i, pt);
addword(r, 0, i, pt);
pt=trie[pt].next[{s[i], r[i]}];
}
trie[pt].cant++;
}
lli query(string &p, string &q, lli ind, lli pt){
deb(p);
deb(q);
deb(ind);
deb(pt);
if(p.size()<=ind){
if(q.size()<=ind){
return trie[pt].cant;
}
else{
if(ind==q.size()){
return trie[pt].cant;
}
lli ans=0;
if(trie[pt].next.find({0, q[ind]})!=trie[pt].next.end()){
ans+=query(p,q, ind+1, trie[pt].next[{0, q[ind]}]);
}
return ans;
}
}
else{
if(q.size()<=ind){
if(ind==p.size()){
return trie[pt].cant;
}
lli ans=0;
if(trie[pt].next.find({p[ind],0})!=trie[pt].next.end()){
ans+=query(p,q, ind+1, trie[pt].next[{p[ind],0}]);
}
return ans;
}
else{
if(ind==p.size() && ind==q.size()){
return trie[pt].cant;
}
lli ans=0;
if(trie[pt].next.find({p[ind],q[ind] })!=trie[pt].next.end()){
ans+=query(p,q,ind+1, trie[pt].next[{p[ind], q[ind]}]);
}
return ans;
}
}
}
void solve(){
lli n;
lli m;
cin>>n>>m;
newNode();
deb(n);
for(lli i=0; i<n; ++i){
deb(i);
string s;
cin>>s;
deb(s);
add(s);
}
for(lli i=0; i<m; ++i){
string p,q;
cin>>p>>q;
reverse(q.begin(), q.end());
lli ans=query(p,q,0,0);
cout<<ans<<endl;
}
}
int main(){
ios::ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
#endif
lli t=1;
// cin>>t;
while(t--){
solve();
}
}
