You've got a string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub> of length |*s*|, consisting of lowercase English letters. There also are *q* queries, each query is described by two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ |*s*|). The answer to the query is the number of substrings of string *s*[*l*<sub class="lower-index">*i*</sub>... *r*<sub class="lower-index">*i*</sub>], which are palindromes.

String *s*[*l*... *r*] = *s*<sub class="lower-index">*l*</sub>*s*<sub class="lower-index">*l* + 1</sub>... *s*<sub class="lower-index">*r*</sub> (1 ≤ *l* ≤ *r* ≤ |*s*|) is a substring of string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub>.

String *t* is called a palindrome, if it reads the same from left to right and from right to left. Formally, if *t* = *t*<sub class="lower-index">1</sub>*t*<sub class="lower-index">2</sub>... *t*<sub class="lower-index">|*t*|</sub> = *t*<sub class="lower-index">|*t*|</sub>*t*<sub class="lower-index">|*t*| - 1</sub>... *t*<sub class="lower-index">1</sub>.
The first line contains string *s* (1 ≤ |*s*| ≤ 5000). The second line contains a single integer *q* (1 ≤ *q* ≤ 10<sup class="upper-index">6</sup>) — the number of queries. Next *q* lines contain the queries. The *i*-th of these lines contains two space-separated integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ |*s*|) — the description of the *i*-th query.

It is guaranteed that the given string consists only of lowercase English letters.
from collections import defaultdict,Counter
from os import path
import sys
from collections import defaultdict
import math
 
def int_inp():
    return int(input())
def mul_inp():
    return map(int,input().split())
def arr_inp():
    return list(map(int,input().split()))
 
 
def is_prime(n):
    prime_flag = 0
    
    if(n > 1):
        for i in range(2, int(math.sqrt(n)) + 1):
            if (n % i == 0):
                prime_flag = 1
                break
        if (prime_flag == 0):
            return True 
        else:
            return False
    else:
        return False
 
def factors(x):
    
    result = []
    i = 1
    
    while i*i <= x:
        
        if x % i == 0:
            result.append(i)
            
            if x//i != i: 
                result.append(x//i)
        i += 1
    
    return sorted(result)
 
 
def prime_factors(x):
    
    result = []
    i = 1
    
    while i*i <= x:
        
        if x % i == 0:
            result.append(i)
        i += 1
    
    return sorted(result)
 
import heapq

def mex(arr):
 
    # Sort the array
    arr=sorted(arr)
    N=len(arr)
    mex = 0
    for idx in range(N):
        if arr[idx] == mex:
 
            # Increment mex
            mex += 1
 
    # return mex as answer
    return mex
from collections import deque


from bisect import bisect_right
import bisect
def isPowerOfTwo(n):
    if (n == 0):
        return False
    while (n != 1):
            if (n % 2 != 0):
                return False
            n = n // 2
             
    return True
def countOfElements(arr, x):
    i = bisect_right(arr, x)
    return i
def dist(x,y):
    return (x**2+y**2)

import math
 
#  Calculates the binomial coefficient nCr using the logarithmic formula
def nCr(n, r):
    # If r is greater than n, return 0
    if r > n:
        return 0
     
    # If r is 0 or equal to n, return 1
    if r == 0 or n == r:
        return 1
    # Initialize the logarithmic sum to 0
    res = 0
     
    # Calculate the logarithmic sum of the numerator and denominator using loop
    for i in range(r):
        # Add the logarithm of (n-i) and subtract the logarithm of (i+1)
        res += math.log(n-i) - math.log(i+1)
    # Convert logarithmic sum back to a normal number
    return round(math.exp(res))

import heapq


import heapq
def lucky(s):
    if len(s)%2==0:
        n=len(s)//2 
        if sum(map(int,list(s[:n])))==sum(map(int,list(s[n:]))):
            return True
    return False 
def solution(iter): 
    
    s=input()
    n=len(s)

    dp=[[0 for i in range(n)] for i in range(n)]

    for i in range(n):
        for j in range(i,n):
            if s[i:j+1]==s[i:j+1][::-1]:
                dp[i][j]=1

    for i in range(n):
        for j in range(1,n):
            dp[i][j]=dp[i][j-1]+dp[i][j]
    
    for i in range(n-2,-1,-1):
        for j in range(n):
            dp[i][j]=dp[i+1][j]+dp[i][j]
   
    q=int_inp()
    for i in range(q):
        x,y=mul_inp()
        print(dp[x-1][y-1])

if(path.exists('input.txt')):
        sys.stdin = open('input.txt', 'r')
        sys.stdout =open('output.txt','w')
for _ in range(1):
    
    solution(_)