// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;
//Fen2d
struct Fen2d
{
int n, m;
vector<vector<int>> bit;
void init(int a, int b){
n = a;
m = b;
bit.assign(n + 1, vector<int> (m + 1, 0));
}
void upd(int x, int y, int val){
for(int i = x; i <= n; i += i & -i){
for(int j = y; j <= m; j += j & -j){
bit[i][j] += val;
}
}
}
int qr(int x, int y){
int ans = 0;
for(int i = x; i > 0; i -= i & -i){
for(int j = y; j > 0; j -= j & -j){
ans += bit[i][j];
}
}
return ans;
}
int qr(int x1, int x2, int y1, int y2){
return qr(x2, y2) - qr(x1 - 1, y2) - qr(x2, y1 - 1) + qr(x1 - 1, y1 - 1);
}
};
//var
const int maxn = 5e5 + 10;
int n, q;
string inp[maxn];
int tin1[maxn], tin2[maxn], tout1[maxn], tout2[maxn];
Fen2d ft;
int eul1 = 0, eul2 = 0;
//trie
struct node
{
int cnt;
array<int, 26> child;
node(){
cnt = 0;
child.fill(-1);
}
};
vector<node> tree1(2);
vector<node> tree2(2); //rev
int id1 = 1, id2 = 1;
int new_node1(){
id1++;
if(id1 >= tree1.size()) tree1.push_back(node());
return id1;
}
int new_node2(){
id2++;
if(id2 >= tree2.size()) tree2.push_back(node());
return id2;
}
void add(string a){
int pos1 = 1;
for(int i=0; i<a.size(); ++i){
int x = a[i];
if(tree1[pos1].child[x - 'A'] == -1){
tree1[pos1].child[x - 'A'] = new_node1();
}
pos1 = tree1[pos1].child[x - 'A'];
}
tree1[pos1].cnt++;
int pos2 = 1;
for(int i = a.size() - 1; i>=0; --i){
int x = a[i];
if(tree2[pos2].child[x - 'A'] == -1){
tree2[pos2].child[x - 'A'] = new_node2();
}
pos2 = tree2[pos2].child[x - 'A'];
}
tree2[pos2].cnt++;
}
pair<int, int> address(string a){
int pos1 = 1;
for(int i=0; i<a.size(); ++i){
int x = a[i];
pos1 = tree1[pos1].child[x - 'A'];
}
int pos2 = 1;
for(int i = a.size() - 1; i>=0; --i){
int x = a[i];
pos2 = tree2[pos2].child[x - 'A'];
}
return make_pair(tin1[pos1], tin2[pos2]);
}
void dfs1(int a){
tin1[a] = ++eul1;
for(int i=0; i<26; ++i){
if(tree1[a].child[i] != -1) dfs1(tree1[a].child[i]);
}
tout1[a] = eul1;
}
void dfs2(int a){
tin2[a] = ++eul2;
for(int i=0; i<26; ++i){
if(tree2[a].child[i] != -1) dfs2(tree2[a].child[i]);
}
tout2[a] = eul2;
}
//
int qr(string p, string q){
int pos1 = 1;
for(int i=0; i<p.size(); ++i){
int x = p[i];
if(tree1[pos1].child[x - 'A'] == -1) return 0;
pos1 = tree1[pos1].child[x - 'A'];
}
int pos2 = 1;
for(int i = q.size() - 1; i>=0; --i){
int x = q[i];
if(tree2[pos2].child[x - 'A'] == -1) return 0;
pos2 = tree2[pos2].child[x - 'A'];
}
return ft.qr(tin1[pos1], tout1[pos1], tin2[pos2], tout2[pos2]);
}
void solve(){
cin >> n >> q;
for(int i=1; i<=n; ++i){
cin >> inp[i];
add(inp[i]);
}
dfs1(1);
dfs2(1);
ft.init(eul1, eul2);
for(int i=1; i<=n; ++i){
pair<int, int> x = address(inp[i]);
ft.upd(x.fi, x.se, 1);
}
while(q--){
string p, q;cin >> p >> q;
cout << qr(p, q) << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
