#include <iostream>
#include <fstream>
#include <vector>
#include <memory.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <assert.h>
 
using namespace std;
 
#define pb push_back
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define sz(s) (int)((s).size())
 
const int INF = 1000000007;
int num[1000055];
int p, sz, last;
int next[1000055][26];
int link[1000055], len[1000055];
int q[1000055];
vector< pair <int, int> > fir[500000];
int cnt[1000055];
int n, x, y;
char s[500055];
map<pair<int,int>, int> qmap;
 
bool cmp(int a, int b) {
    return (len[a] > len[b]);
}
 
bool cmpPair(pair<int, int> a, pair<int, int> b) {
    return (a.first < b.first || (a.first == b.first && a.second < b.second));
}

// precalculation suffix automation
 
void sa_build(){
    int l = strlen(s);
    sz = 1;
    last = 0;
    len[0] = 0;
    link[0] = -1;
    for (int i = 0; i < l; ++i) {
        int c = s[i] - 'a';
        int cur = sz++;
        cnt[cur] = 1;
        len[cur] = len[last] + 1;
        for (p = last; p != -1 && !next[p][c]; p = link[p]) next[p][c] = cur;
        if (p == -1) link[cur] = 0;
        else {
            int q = next[p][c];
            if (len[q] == len[p] + 1) link[cur] = q;
            else {
                int clone = sz++;
                len[clone] = len[p] + 1;
                link[clone] = link[q];
                for (int j = 0; j < 26; ++j) next[clone][j] = next[q][j];
                for (; p != -1 && next[p][c] == q; p = link[p]) next[p][c] = clone;
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }
    // calculated number of elements in each class 
    for (int i = 0; i < sz; ++i) q[i] = i;
    sort(q, q + sz, cmp);
    for (int i = 0; i < sz; ++i) {
        int tmp = q[i];
        cnt[link[tmp]] += cnt[tmp];
    }
    // solve problem offline
    for (int i = 1; i < sz; ++i) {
        int l, r;
        l = len[link[i]] + 1;
        r = len[i];
 
        fir[cnt[i]].push_back(make_pair(l, -1));
        fir[cnt[i]].push_back(make_pair(r, INF));
    }
}
 
int main(){
    gets(s);
    sa_build();
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int cnt, l;
        scanf("%d%d", &l, &cnt);
        fir[cnt].push_back(make_pair(l, i));
    }
    int len = strlen(s);
    for (int i = 1; i <= len; ++i) {
        sort(fir[i].begin(),fir[i].end(), cmpPair);
        int ret = 0;
        for (int j = 0; j < (int)fir[i].size(); ++j) {
            if (fir[i][j].second == -1) ret++;
            else if (fir[i][j].second == INF) ret--;
            else {
                num[fir[i][j].second] = ret;
            }
        }
    }
    for (int i = 0; i < n; ++i) printf("%d\n", num[i]);
    return 0;
}