//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5, block = 330, M = 2e6;
vector<int> pre[M + 1], suf[M + 1], adj[M + 1], ans[M + 1];
bool built[M + 1];
bitset<N + 1> visited;
struct Trie
{
struct node
{
int child[26];
node()
{
memset(child, -1, sizeof(child));
}
};
vector<node> tree;
void new_node()
{
node tmp;
tree.push_back(tmp);
}
void reset()
{
tree.clear();
new_node();
}
int add_query(string &s)
{
int id = 0;
for (char c : s)
{
int w = c - 'A';
if (tree[id].child[w] == -1)
{
tree[id].child[w] = tree.size();
new_node();
}
id = tree[id].child[w];
}
return id;
}
void add_pattern(int i, int t, string &s)
{
int id = 0;
for (char c : s)
{
int w = c - 'A';
if (tree[id].child[w] == -1)
{
return ;
}
id = tree[id].child[w];
if (t)
{
suf[id].push_back(i);
}
else
{
pre[id].push_back(i);
}
}
}
} tree;
void build(int u)
{
built[u] = true;
visited.reset();
sort(adj[u].begin(), adj[u].end());
adj[u].erase(unique(adj[u].begin(), adj[u].end()), adj[u].end());
for (int i : pre[u])
{
visited[i] = true;
}
for (int v : adj[u])
{
int res = 0;
for (int i : suf[v])
{
res += visited[i];
}
ans[u].push_back(res);
}
}
string s[N + 1], p[N + 1], q[N + 1];
int n, m, a[N + 1], b[N + 1];
void read()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
{
cin >> s[i];
}
for (int i = 1; i <= m; ++ i)
{
cin >> p[i] >> q[i];
}
}
void solve()
{
tree.reset();
for (int i = 1; i <= m; ++ i)
{
a[i] = tree.add_query(p[i]);
//cerr << a[i] << '\n';
}
for (int i = 1; i <= n; ++ i)
{
tree.add_pattern(i, 0, s[i]);
reverse(s[i].begin(), s[i].end());
}
tree.reset();
for (int i = 1; i <= m; ++ i)
{
reverse(q[i].begin(), q[i].end());
b[i] = tree.add_query(q[i]);
}
for (int i = 1; i <= n; ++ i)
{
tree.add_pattern(i, 1, s[i]);
}
for (int i = 1; i <= m; ++ i)
{
adj[a[i]].push_back(b[i]);
//cerr << a[i] << ' ' << b[i] << '\n';
}
for (int i = 1; i <= m; ++ i)
{
if (pre[a[i]].size() <= block)
{
int res = 0;
for (int u : pre[a[i]])
{
res += binary_search(suf[b[i]].begin(), suf[b[i]].end(), u);
}
cout << res << '\n';
}
else
{
if (!built[a[i]])
{
build(a[i]);
}
int j = lower_bound(adj[a[i]].begin(), adj[a[i]].end(), b[i]) - adj[a[i]].begin();
cout << ans[a[i]][j] << '\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case #" << __ << ":" << '\n';
read();
solve();
}
}
