#include <bits/stdc++.h>
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end()
#define mp make_pair
using namespace std;
const ll N = 1e6;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2;
const ll pe2 = 570210983;
const ld eps = 1e-6;
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
#ifdef NURS
freopen("main.in", "r", stdin);
freopen("main.out", "w", stdout);
#endif
}
int n, m;
string s[N], l[N], r[N]; ll hashl[N], hashr[N], hashl2[N], hashr2[N];
map<string, int> was, was2, used, used2;
map<string, int> hsh, hsh2;
vector<int> g[N];
map<pair<string, string>, int> add;
string now = "";
map<int, string> hashw;
void dfs(int v, int len, int p)
{
if (len == 2)
{
add[{now, hashw[v]}]++;
}
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (len + 1 <= 2 && to != p)
dfs(to, len + 1, v);
}
}
main()
{
data();
ios_base::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= m; i++)
{
cin >> l[i] >> r[i];
was[l[i]] = 1, was2[r[i]] = 1;
}
//хеширую
for (int i = 1; i <= m; i++)
{
ll hash = 0;
for (int j = 0; j < l[i].size(); j++)
hash = hash * pe % mod + (l[i][j] - 'A' + 1), hash = hash % mod;
hashl[i] = hash;
hashl2[i] = hash;
hash = 0;
for (int j = 0; j < r[i].size(); j++)
hash = hash * pe % mod + (r[i][j] - 'A' + 1), hash = hash % mod;
hashr[i] = hash;
hashr2[i] = hash;
}
//просто сжатие хешей
sort(hashl2 + 1, hashl2 + m + 1);
sort(hashr2 + 1, hashr2 + m + 1);
int sz = unique(hashl2 + 1, hashl2 + m + 1) - hashl2 - 1;
int sz2 = unique(hashr2 + 1, hashr2 + m + 1) - hashr2 - 1;
for (int i = 1; i <= m; i++)
{
hashl[i] = lower_bound(hashl2 + 1, hashl2 + sz + 1, hashl[i]) - hashl2;
hashr[i] = lower_bound(hashr2 + 1, hashr2 + sz2 + 1, hashr[i]) - hashr2;
hsh[l[i]] = hashl[i];
hsh2[r[i]] = hashr[i];
hashw[hsh[l[i]] + 9 * n] = l[i];
}
//добавил ребра
for (int i = 1; i <= n; i++)
{
string q = "";
for (int j = 0; j < s[i].size(); j++)
{
q += s[i][j];
if (was[q])
{
g[i].pb(hsh[q] + 9 * n), g[hsh[q] + 9 * n].pb(i);
// cout << hsh[q] + 9 * n << " " << i << '\n';
// cout << i << " " << hsh[q] + 9 * n << '\n';
}
}
q = "";
for (int j = s[i].size() - 1; j >= 0; j--)
{
q = s[i][j] + q;
if (was2[q])
{
g[i].pb(hsh2[q] + 4 * n), g[hsh2[q] + 4 * n].pb(i);
// cout << i + n << " " << hsh2[q] + 4 * n << '\n';
// cout << hsh2[q] + n * 4 << " " << i + n << '\n';
}
}
}
//end
for (int i = 1; i <= m; i++)
{
if (!used2[r[i]] && hsh2[r[i]] > 0)
{
now = r[i];
dfs(hsh2[r[i]] + 4 * n, 0, 0);
used2[r[i]] = 1;
}
cout << add[{r[i], l[i]}] << '\n';
}
}
