#include <bits/stdc++.h>
#include <string>

using namespace std;
string orig_str;

int longest_subseq(string str){
    int size = str.length();
    int L[size][size];
    int j;
    
    for(int i = 0; i < size; i++){
        L[i][i] = 1;
    }
    
    for(int x=2; x<=size; x++){
        
        for(int i = 0; i < size-x+1; i++){
            j = i+x-1;
            if(str[i] == str[j] && x == 2){
                L[i][j] = 2;
            }
            else if(str[i] == str[j]){
                L[i][j] = L[i+1][j-1] + 2;
            }
            else{
                L[i][j] = max(L[i][j-1], L[i+1][j]);
            }
        }
    }
    return L[0][size-1];
}


int max(int a, int b){
    if(a>b){
        return a;
    }
    else return b;
}

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

int answerQuery(int l, int r) {
    // Return the answer for this query modulo 1000000007.
    string new_str;
    int iter = 0;
    for(int i = l - 1; i < r; i++){
        new_str+=orig_str[i];
        iter++;
    }
    //cerr << new_str << endl;
    return longest_subseq(new_str);
}

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);
        cout << result << endl;
    }
    return 0;
}