#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 2e5 + 5, base = 131;
const ll llinf = 1e18;
vector<ll> Hash[maxn];
vector<pair<ll, int>> need[maxn];
int N, M;
int res[maxn];
string p[maxn], q[maxn], str[maxn];
ll POW[maxn];
map<ll, vector<int>> pref;
ll get(int id, int l, int r)
{
if(l == 0) return Hash[id][r];
return Hash[id][r] - Hash[id][l - 1] * POW[r - l + 1];
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
#endif // LOCAL
POW[0] = 1;
for(int i = 1; i < maxn; ++i)
POW[i] = POW[i - 1] * base;
cin >> N >> M;
for(int i = 1; i <= N; ++i){
cin >> str[i];
Hash[i].assign(str[i].size(), 0);
for(int j = 0; j < (int)str[i].size(); ++j){
if(j) Hash[i][j] = Hash[i][j - 1] * base + str[i][j];
else Hash[i][j] = str[i][j];
pref[Hash[i][j]].pb(i);
}
}
for(int i = 1; i <= M; ++i){
cin >> p[i] >> q[i];
ll hashp = 0;
for(int j = 0; j < (int)p[i].size(); ++j){
hashp = hashp * base + p[i][j];
}
ll hashq = 0;
for(int j = 0; j < (int)q[i].size(); ++j){
hashq = hashq * base + q[i][j];
}
for(auto & id : pref[hashp]) need[id].eb(hashq, i);
}
for(int i = 1; i <= N; ++i){
for(auto id : need[i]){
if(str[i].size() >= q[id.se].size()){
if(get(i, str[i].size() - q[id.se].size(), str[i].size() - 1) == id.fi)
res[id.se]++;
}
}
}
for(int i = 1; i <= M; ++i)
cout << res[i] << '\n';
}
