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 array import array
from sys import stdin ,stdout ,setrecursionlimit
from threading import  stack_size , Thread
setrecursionlimit(2**31-1)
input=stdin.readline
def print(*args, end='\n', sep=' ') -> None:
    stdout.write(sep.join(map(str, args)) + end)


def palindrome(lef , righ):
    while (lef<=righ):
        if (st[lef]!=st[righ]):return 0 
        lef+=1 
        righ-=1
    return 1 
    

def dp(ind ,last):
    if ind==lenth:return 
    if (last,ind) in mem :return
    mem[(last,ind)]=palindrome(last , ind)
    dp(ind+1,ind+1)
    if ind!=lenth-1:
        dp(ind+1 , last )


st=input().strip() ; lenth=len(st) ; mem={}


def solve():
    dp(0,0) 
    for i in range(lenth):
        for j in range(i,lenth):
            if j==i :continue
            mem[(i,j)]+=mem[(i,j-1 )]
            
    for i in range(lenth):
        for j in range(1,i+1):
            mem[(j,i)]+=mem[(j-1,i)]
    for _ in range(int(input())):
        l,r=map(int,input().split())
        l-=1 ; r-=1 
        if (l==0): print(mem[(r,r)])
        else: print(mem[(r,r)]-mem[(l-1,r)])

stack_size(10**8) 
Thread(target=solve).start()
