#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
const int MAX_N = 2e6 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
int n, m, cnt;
const char clist[4] = {'C','U','G','A'};
struct snode{
char f, s;
int ind;
};
struct node{
int father , sz;
vector<snode> child;
node(){
sz =0;
cnt++;
}
};
node v[MAX_N];
void addstring(string& s){
int len = s.length();
int curnode = 0;
for (int i = 0;i<len;i++){
//cout << curnode <<endl;
int found = -1;
for (auto k : v[curnode].child){
if (k.f==s[i]&&k.s==s[len-i-1]){
found = k.ind;
break;
}
}
if (found==-1){
node newnode;
newnode.father = curnode;
v[curnode].child.push_back({s[i],s[len-i-1],cnt});
v[cnt] = newnode;
found = cnt;
}
curnode = found;
}
while (curnode != -1){
//cout << curnode <<" A"<<endl;
v[curnode].sz++;
curnode = v[curnode].father;
//cout << curnode <<endl;
}
}
int findstring(int i, int ptr, string& a, string& b, int& mx){
if (ptr==mx) return v[i].sz;
int ret = 0;
if (a[ptr]=='0'){
for (auto k : v[i].child)
if (k.s==b[ptr]) ret += findstring(k.ind,ptr+1,a,b,mx);
return ret;
}
if (b[ptr]=='0'){
for (auto k : v[i].child)
if (k.f==a[ptr]) ret += findstring(k.ind,ptr+1,a,b,mx);
return ret;
}
//cout << b <<endl;
for (auto k : v[i].child)
if (k.f==a[ptr]&&k.s==b[ptr]) ret+= findstring(k.ind,ptr+1,a,b,mx);
return ret;
}
void solve() {
node newnode;
cnt = 0;
newnode.father = -1;
v[0] = newnode;
cin >> n >> m;
string s, a, b;
while (n--){
cin >> s;
addstring(s);
}
while (m--){
cin >> a >> b;
reverse(b.begin(),b.end());
while (a.length()>b.length()) b.append("0");
while (b.length()>a.length()) a.append("0");
int mx = a.length();
cout << findstring(0,0,a,b,mx)<<"\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
