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.
def count_palindromes(s):
    # Modify the string to include special characters
    modified_s = '#'.join('^{}$'.format(s))
    n = len(modified_s)
    p = [0] * n  # palindrome lengths
    c = r = 0   # center and right boundary of the rightmost palindrome

    for i in range(1, n - 1):
        if i < r:
            mirror = 2 * c - i  # mirror position of i
            p[i] = min(r - i, p[mirror])

        # Attempt to expand the palindrome centered at i
        while modified_s[i + 1 + p[i]] == modified_s[i - 1 - p[i]]:
            p[i] += 1

        # Update the center and right boundary if necessary
        if i + p[i] > r:
            c = i
            r = i + p[i]

    # Count the number of palindromic substrings
    count = sum((length + 1) // 2 for length in p)
    return count


# Read input
s = input().strip()
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]

# Process queries
results = []
for li, ri in queries:
    substr = s[li - 1:ri]  # Extract the substring
    count = count_palindromes(substr)
    results.append(count)

# Print the results
print(*results)
