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.
s = input()
n = len(s)
dp = [[0 for i in range(n)] for j in range(n)]
count = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	dp[i][i] = 1
	count[i][i] = 1
for i in range(n-1,-1,-1):
	for j in range(i,n):
		if s[i]==s[j] and (j-i<2 or dp[i+1][j-1]):
			dp[i][j] = 1
for i in range(1,n):
	for j in range(i-1,-1,-1):
		if j==i-1:
			if dp[j][i]:
				count[j][i] = 3
			else:
				count[j][i] = 2
		else:
			count[j][i] = count[j+1][i] + count[j][i-1] - count[j+1][i-1]
			if dp[j][i]:
				count[j][i] += 1
# for i in count:
	# print (*i)
for i in range(int(input())):
	l,r = map(int,input().split())
	print (count[l-1][r-1])