#include <bits/stdc++.h>
using namespace std;
// ad astra per aspera
#define ll long long
#define ld long double
#define ub upper_bound
#define lb lower_bound
#define check(a, k) ((a) & (1LL << k))
#define fi first
#define se second
#define pll pair<ll, ll>
#define pll_ll pair<pll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x / gcd(x, y)) * y)
#define forn(i, n) for (ll i = 0; i < n; i++)
#define rep(i, start, n) for (ll i = start; i <= n; i++)
#define pow2(x) (x) * (x)
const ll M = 1e6 + 5, inf = 1e18 + 5, mod = 1e9 + 7, base[] = {131, 313};
ll n, t, u, v, w, k, m, re = 0, q, ss;
struct Trie
{
struct node
{
node *child[26];
int exist;
vector<int> ss;
node()
{
forn(i, 26) child[i]=NULL;
exist=0;
}
};
int cur;
node *root;
Trie() : cur(0) {root=new node(); }
void add_string(string s, int i)
{
node *p=root;
for(auto x:s)
{
int c=x-'A';
if(p->child[c]==NULL) p->child[c]=new node();
p=p->child[c];
p->ss.push_back(i);
}
p->exist++;
}
// bool delete_string_recursive(node *p, string& s, int i)
// {
// if (i != (int)s.size()) {
// int c = s[i] - 'a';
// bool isChildDeleted = delete_string_recursive(p->child[c], s, i + 1);
// if (isChildDeleted) p->child[c] = NULL;
// }
// else p->exist--;
// if (p != root) {
// p->cnt--;
// if (p->cnt == 0) {
// delete(p);
// return true;
// }
// }
// return false;
// }
// void delete_string(string s)
// {
// if(find_string(s)) delete_string_recursive(root, s, 0);
// }
int find_string(string s, int l, int r) {
if(l>r) return 0;
node* p = root;
for (auto f : s) {
int c = f - 'A';
if (p->child[c] == NULL) return false;
p = p->child[c];
}
return ub(all(p->ss), r)-lb(all(p->ss), l);
}
// string find_kth_str(ll k)
// {
// string re="";
// node *p=root;
// while(1)
// {
// if(p->exist>=k) break;
// k-=p->exist;
// forn(i, 26) if(p->child[i]!=NULL)
// {
// auto nxt = p->child[i];
// if (nxt->cnt >= k) {
// re+=char(i + 'a');
// p=nxt;
// break;
// }
// k -= nxt->cnt;
// }
// }
// return re;
// }
};
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>t;
Trie trie;
vector<string> s(n);
forn(i, n) cin>>s[i];
sort(all(s));
string sp;
forn(i, n)
{
sp=s[i]; //cout<<sp<<' ';
reverse(all(sp));
trie.add_string(sp, i);
}
while(t--)
{
string pre, suf;
cin>>pre>>suf;
reverse(all(suf));
ll l=lb(all(s), pre)-s.begin(), r=ub(all(s), pre+"[")-s.begin();
//cout<<l<<' '<<r<<' ';
cout<<trie.find_string(suf, l, r-1)<<'\n';
}
return 0;
}
