import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class LongestPalinSubstring 
{
    static void printSubStr(String str, int low, int high) {
        System.out.println(str.substring(low, high + 1));
    }
 
    static int longestPalSubstr(String str) {
        int n = str.length();   // get length of input string
 
         boolean table[][] = new boolean[n][n];
        int maxLength = 1;
        for (int i = 0; i < n; ++i)
            table[i][i] = true;
 
        // check for sub-string of length 2.
        int start = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (str.charAt(i) == str.charAt(i + 1)) {
                table[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
         
        // Check for lengths greater than 2. k is length
        // of substring
        for (int k = 3; k <= n; ++k) {
             
                  // Fix the starting index
            for (int i = 0; i < n - k + 1; ++i) 
            {
               int j = i + k - 1;
 
               if (table[i + 1][j - 1] && str.charAt(i) == 
                                          str.charAt(j)) {
                    table[i][j] = true;
 
                    if (k > maxLength) {
                        start = i;
                        maxLength = k;
                    }
                }
            }
        }
        
         
        return maxLength; // return length of LPS
    }
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
 
        StringBuffer sb=new StringBuffer(s.next());
        int q = s.nextInt();
        for(int i=0;i<q;i++)
        {
            int l = s.nextInt();
            int r = s.nextInt();
            String str = sb.substring(l,r);
        
            System.out.println(longestPalSubstr(str));
        }
    }
}