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.
# ﷽
import sys
input = lambda: sys.stdin.readline().strip()
def inlst():return [int(i) for i in input().split()]
oo=float('inf')

def solve():
    s=input()
    n=len(s)
    q=[inlst() for _ in range(int(input()))]
    dp=[[0]*(n) for _ in range(n)]
    for i in range(n):dp[i][i]=1
    for i in range(1,n):
        if s[i]==s[i-1]:
            dp[i][i-1]=1
        for j in range(i-2,-1,-1):

            if s[i]==s[j]:
                dp[i][j]=dp[i-1][j+1]
    mat=NumMatrix(dp)
    for l,r in q:
        print(mat.sumRegion(l-1,l-1,r-1,r-1))
    

def main():
    # for i in range(int(input())):
        solve()
class NumMatrix:

    def __init__(self, matrix):
        self.preSum = [[0 for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]
        for i in range(1, len(matrix) + 1):
            for j in range(1, len(matrix[0]) + 1):
                self.preSum[i][j] = self.preSum[i - 1][j] + self.preSum[i][j - 1] - self.preSum[i - 1][j - 1] + matrix[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.preSum[row2 + 1][col2 + 1] - self.preSum[row1][col2 + 1] - self.preSum[row2 + 1][col1] + self.preSum[row1][col1]   

if __name__ == "__main__":
    main()
