import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.StringTokenizer;

public class automatictrading_artur {

  static final int MAX = 100100, LOG = 17;

  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    PrintStream out = new PrintStream(System.out);
    StringTokenizer str;

    String s;
    int[] a = new int[MAX];
    int[] p = new int[MAX], q = new int[MAX], cnt = new int[MAX];
    int[][] c = new int[LOG][MAX];

    while (true) {
      s = in.readLine();
      if ("*".equals(s))
        break;

      int n = s.length(), logn;
      for (int i = 0; i < n; i++) {
        char stock = s.charAt(i);
        if ('a' <= stock && stock <= 'z')
          a[i] = stock - 'a';
        else
          a[i] = stock - 'A' + 26;
      }

      // suffix-array construction: base case
      Arrays.fill(cnt, 0);
      for (int i = 0; i < n; i++)
        cnt[a[i]]++;
      for (int i = 1; i < cnt.length; i++)
        cnt[i] += cnt[i - 1];
      for (int i = 0; i < n; i++)
        p[--cnt[a[i]]] = i;
      c[0][p[0]] = 0;
      int eqclass = 1;
      for (int i = 1; i < n; i++) {
        if (a[p[i]] != a[p[i - 1]])
          eqclass++;
        c[0][p[i]] = eqclass - 1;
      }

      // suffix-array construction: induction step
      for (logn = 0; (1 << logn) < n; logn++) {
        for (int i = 0; i < n; i++) {
          q[i] = p[i] - (1 << logn);
          if (q[i] < 0)
            q[i] += n;
        }
        Arrays.fill(cnt, 0);
        for (int i = 0; i < n; i++)
          cnt[c[logn][q[i]]]++;
        for (int i = 1; i < eqclass; i++)
          cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--)
          p[--cnt[c[logn][q[i]]]] = q[i];
        c[logn + 1][p[0]] = 0;
        eqclass = 1;
        for (int i = 1; i < n; i++) {
          int mid1 = (p[i] + (1 << logn)) % n, mid2 = (p[i - 1] + (1 << logn)) % n;
          if (c[logn][p[i]] != c[logn][p[i - 1]] || c[logn][mid1] != c[logn][mid2])
            eqclass++;
          c[logn + 1][p[i]] = eqclass - 1;
        }
      }

      // queries in O(logn)
      int queries = Integer.parseInt(in.readLine());
      while (queries-- > 0) {
        str = new StringTokenizer(in.readLine());
        int x = Integer.parseInt(str.nextToken());
        int y = Integer.parseInt(str.nextToken());

        int result = 0;
        for (int i = logn; i >= 0 && x < n && y < n; i--)
          if (c[i][x] == c[i][y] && x + (1 << i) <= n && y + (1 << i) <= n) {
            result += 1 << i;
            x += 1 << i;
            y += 1 << i;
          }

        out.println(result);
      }
    }

    in.close();
    out.close();
  }
}