#include <bits/stdc++.h>
            
using namespace std;

typedef unsigned long long ull;

int n, m;
int P = 131;
unordered_map<ull,vector<int> > mm;
    
int main()
{
    freopen("engzam.in", "r", stdin);
    freopen("engzam.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
            
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        string s;
        int num;
        cin >> s >> num;
        ull las = 0;
        for(int j = 0; j < s.length(); ++j)
        {
            las = las*P+(int)s[j];
            auto pos = lower_bound(mm[las].begin(),mm[las].end(),num);
            if(mm[las].size() == 0)
                mm[las].push_back(num);
            else
                mm[las].insert(pos,num);
        }
    }
    for(int i = 1; i <= m; ++i)
    {
        string s;
        int l;
        cin >> s >> l;
        ull las = 0;
        for(int j = 0; j < s.length(); ++j)
            las = las*P+(int)s[j];
        int pos = lower_bound(mm[las].begin(),mm[las].end(),l)-mm[las].begin();
        cout << mm[las].size()-pos << '\n';
    }
    
   	return 0;
}