Untitled

#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#include 
 
using namespace std;
const int maxn = 5050;
bool is_palindrome[maxn][maxn];
int dp[maxn][maxn];
char s[maxn];
int rec(int i, int j) {
    if(i > j) {
        return 0;
    }
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    int result = 0;
    if(is_palindrome[i][j]) {
        result = 1;
    }
    result += rec(i + 1, j) + rec(i, j - 1) - rec(i + 1, j - 1);
    return dp[i][j] = result;
}
int main() {
    ios::sync_with_stdio(0);
    scanf("%s", s);
    int n = strlen(s);
    memset(is_palindrome, false, sizeof is_palindrome);
    memset(dp, -1, sizeof dp);
    for(int sz = 1; sz <= n; sz++) {
        for(int at = 0; at <= n - sz; at++) {
            if(sz <= 2) {
                if(s[at] == s[at + sz - 1]) {
                    is_palindrome[at][at + sz - 1] = true;
                }
            }
            else if(s[at] == s[at + sz - 1]) {
                is_palindrome[at][at + sz - 1] = is_palindrome[at + 1][at + sz - 2];
            }
            
        }
    }
    for(int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    for(int i = 0; i + 1 < n; i++) {
        if(s[i] == s[i + 1]) {
            dp[i][i + 1] = 3;
        }
        else {
            dp[i][i + 1] = 2;
        }
    }
    rec(0, n - 1);
    int t;
    scanf("%d", &t);
    int L, R;
    while(t--) {
        scanf("%d%d", &L, &R);
        printf("%d\n", dp[L - 1][R - 1]);
    }
    return 0;
}