#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>

int pod = 1019, mod = 1000000033;
int pref[1000002], pot[1000002];

int hasz(int l, int r) {
    int res = pref[r] - pref[l-1] * pot[r-l+1] % mod;
    if (res < 0)
        res += mod;
    return res;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    pot[0] = 1;
    for (int i = 1; i <= 200000; i++) {
        pot[i] = pot[i-1] * pod % mod;
    }
    while (true) {
        string slo;
        cin >> slo;
        if (slo == "*")
            break;
        slo = "%" + slo;
        pref[0] = 0;
        for (int i = 1; i < sz(slo); i++) {
            pref[i] = pref[i-1] * pod + slo[i];
            pref[i] %= mod;
        }
        int q;
        cin >> q;
        while (q--) {
            int l, r;
            cin >> l >> r;
            l++; r++;
            int pocz = 0, kon = sz(slo) - r;
            while (pocz < kon) {
                int mid = (pocz + kon + 1) / 2;
                if (hasz(l, l + mid - 1) == hasz(r, r + mid - 1)) {
                    pocz = mid;
                } else {
                    kon = mid - 1;
                }
            }
            cout << pocz << "\n";
        }
    }
}