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 sys import stdin, stdout
from collections import Counter, defaultdict
from itertools import permutations, combinations
from math import sqrt
from bisect import bisect
raw_input = stdin.readline
pr = stdout.write
mod=10**9+7

def ni():
    return int(raw_input())


def li():
    return map(int,raw_input().split())


def pn(n):
    stdout.write(str(n)+'\n')


def pa(arr):
    pr('\n'.join(map(str,arr))+'\n')

# fast read function for total integer input

def inp():
    # this function returns whole input of
    # space/line seperated integers
    # Use Ctrl+D to flush stdin.
    return list(map(int,stdin.read().split()))

#range = xrange # not for python 3.0+

s=raw_input().strip()
n=len(s)
d=[[0 for i in range(n+1)] for j in range(n+1)]
dp=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    d[i][i]=1
    d[i+1][i]=1
    dp[i][i]=1
    
for i in range(2,n+1):
    for j in range(n-i+1):
        if s[j]==s[i+j-1] and d[j+1][i+j-2]:
            d[j][i+j-1]=1
        dp[j][i+j-1]=dp[j][i+j-2]+dp[j+1][i+j-1]-dp[j+1][j+i-2]+d[j][i+j-1]
arr=[]
inp=inp()
pos=1
for q in range(inp[0]):
    l,r=inp[pos],inp[pos+1]
    pos+=2
    arr.append(dp[l-1][r-1])
pa(arr)
