#include <bits/stdc++.h>

using namespace std;

void initialize(string s) {
    // This function is called once before all queries.
}

int answerQuery(int l, int r,string s) {
    // Return the answer for this query modulo 1000000007.
    int n = r-l+1; // get length of input string
    char str[n];
    int k=0;
    for(int i=l;i<=r;i++)
    {
        str[k]=s[i];
        k++;
    }   
   bool table[n][n];
    memset(table, 0, sizeof(table));
 
    // All substrings of length 1 are palindromes
    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[i] == str[i+1])
        {
            table[i][i+1] = true;
            start = i;
            maxLength = 2;
        }
    }
    maxLength++;
    // 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[i] == str[j])
            {
                table[i][j] = true;
 
                if (k > maxLength)
                {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }   
       return (maxLength-1)%1000000007;
}

int main() {
    string s;
    cin >> s;
    initialize(s);
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int l;
        int r;
        cin >> l >> r;
        int result = answerQuery(l, r,s);
        cout << result << endl;
    }
    return 0;
}