/* May 18 2020 */
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
#include <random>
#include <iostream>
#include <string>
#define ll long long
#define ri string::reverse_iterator
using namespace std;
ll n, m;
struct trie {
map<char, trie*> children;
vector<ll> indexes;
void insert(ri l, ri r, ll idx) {
indexes.push_back(idx);
if (l == r) return;
char c = *l;
if (children.find(c) == children.end())
children[c] = new trie();
children[c]->insert(next(l), r, idx);
}
ll cnt(ri l, ri r, ll tl, ll tr) {
if (l == r)
return lower_bound(indexes.begin(), indexes.end(), tr) -
lower_bound(indexes.begin(), indexes.end(), tl);
char c = *l;
if (children.find(c) == children.end()) return 0;
return children[c]->cnt(next(l), r, tl, tr);
}
} main_trie;
int main(void) {
scanf("%lld %lld", &n, &m);
vector<string> vals(n);
for (ll i = 0; i < n; ++i) cin >> vals[i];
sort(vals.begin(), vals.end());
for (ll i = 0; i < n; ++i)
main_trie.insert(vals[i].rbegin(), vals[i].rend(), i);
while (m --) {
string x, y; cin >> x >> y;
ll l = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
++x.back();
ll r = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
printf("%lld\n", main_trie.cnt(y.rbegin(), y.rend(), l, r));
}
return 0;
}
