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 collections
import math

def bit(c):
    return 1 << ((ord(c) - 1) & 31)

def neighbors(sig):
    yield sig
    for i in range(26):
        yield sig ^ (1 << i)


class PPCounter(object):
    def __init__(self):
        self.count = 0
        self._sigcount = collections.Counter({0: 1})
        self._leftsig = 0
        self._rightsig = 0

    def pushleft(self, c):
        self._leftsig ^= bit(c)
        for sig in neighbors(self._leftsig):
            self.count += self._sigcount[sig]
        self._sigcount[self._leftsig] += 1

    def popleft(self, c):
        self._sigcount[self._leftsig] -= 1
        for sig in neighbors(self._leftsig):
            self.count -= self._sigcount[sig]
        self._leftsig ^= bit(c)

    def pushright(self, c):
        self._rightsig ^= bit(c)
        for sig in neighbors(self._rightsig):
            self.count += self._sigcount[sig]
        self._sigcount[self._rightsig] += 1

    def popright(self, c):
        self._sigcount[self._rightsig] -= 1
        for sig in neighbors(self._rightsig):
            self.count -= self._sigcount[sig]
        self._rightsig ^= bit(c)

ans = [int]*100000

def ppcount(s, intervals):
    sqrtn = int(math.sqrt(len(s)))
    intervals = sorted(
        intervals, key=lambda interval: (interval[0] // sqrtn, interval[1]))
    l = 0
    r = -1
    ctr = PPCounter()
    for interval in intervals:
        il, ir, id = interval
        while l > il:
            l -= 1
            ctr.pushleft(s[l])
        while r < ir:
            r += 1
            ctr.pushright(s[r])
        while l < il:
            ctr.popleft(s[l])
            l += 1
        while r > ir:
            ctr.popright(s[r])
            r -= 1
        ans[id] = ctr.count


def solve():
    s = input()
    n = int(input())
    intervals = []
    for i in range(n):
        l, r = map(int, input().split())
        intervals.append((l-1, r-1, i))
    ppcount(s, intervals)
    for i in range(n):
        print(ans[i])


solve()
