Queries for Number of Palindromes
You've got a string s = s1s2... s|s| of length |s|, consisting of lowercase English letters. There also are q queries, each query is described by two integers li, ri (1 ≤ li ≤ ri ≤ |s|). The answer to the query is the number of substrings of string s[li... ri], which are palindromes.String s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s1s2... s|s|.String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t1t2... t|t| = t|t|t|t| - 1... t1.
Consider the fourth query in the first test case. String s[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».
The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106) — the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the description of the i-th query.It is guaranteed that the given string consists only of lowercase English letters.
Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def primes(n):
    ans = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ans.append(i)
            while n % i == 0:
                n //= i
        if n == 1:
            break
    if n != 1:
        ans.append(n)
    return ans

def countSetBits(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans

def factors(n):
    ans = []
    rev = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i * i == n:
                ans.append(i)
                continue
            ans.append(i)
            rev.append(n // i)
    return ans + rev[::-1]

def factorial(x, mod):
    if x == 1 or x == 0 or x >= mod:
        return 1
    ans = 1
    for i in range(2, x + 1):
        ans *= i
        if ans % mod == 0:
            return 0
        ans %= mod
    return ans
    return x % mod * factorial(x - 1, mod) % mod
s = input()
q = int(input())
n = len(s)
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i] = 1
for i in range(n - 1):
    if s[i] == s[i + 1]:
        dp[i][i + 1] = 1
for l in range(3, n + 1):
    for start in range(n + 1 - l):
        end = start + l - 1
        if s[start] == s[end] and dp[start + 1][end - 1]:
            dp[start][end] = 1
for i in range(n - 1):
    for j in range(i + 1, n):
        dp[i][j] += dp[i][j - 1]
for j in range(1, n):
    for i in range(j - 1, -1, -1):
        dp[i][j] += dp[i + 1][j]
for i in range(q):
    [l, r] = list(map(int, input().split()))
    l -= 1
    r -= 1
    ans = dp[l][r]
    print(ans)
import os
import sys
from io import BytesIO, IOBase

def main():
    s = input()
    n = len(s)
    pl = [[0] * n for _ in range(n + 1)]
    dp = [[0] * n for _ in range(n + 1)]
    for i in range(n):
        pl[i][i] = dp[i][i] = 1
        pl[i + 1][i] = 1
    for ln in range(2, n + 1):
        for st in range(n - ln + 1):
            j = st + ln - 1
            if ln == 0:
                pl[i][j] = 1
            elif s[st] == s[j]:
                if ln == 1:
                    pl[i][j] = 1
                else:
                    pl[st][j] = pl[st + 1][j - 1]
            else:
                pl[st][j] = int(s[st] == s[j] and pl[st + 1][j - 1])
    for ln in range(2, n + 1):
        for st in range(n - ln + 1):
            dp[st][st + ln - 1] = dp[st][st + ln - 2] + dp[st + 1][st + ln - 1] - dp[st + 1][st + ln - 2] + pl[st][st + ln - 1]
    for _ in range(int(input())):
        (l, r) = map(int, input().split())
        print(dp[l - 1][r - 1])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    for t in range(1):
        main()
import os
import sys
from io import BytesIO, IOBase

def main():
    s = input()
    n = len(s)
    palin = [[0 for _ in range(n)] for _ in range(n)]
    dp = [[0 for _ in range(n)] for _ in range(n)]
    for sz in range(n):
        for i in range(n - sz):
            j = i + sz
            if sz == 0:
                palin[i][j] = 1
            elif s[i] == s[j]:
                if sz == 1:
                    palin[i][j] = 1
                else:
                    palin[i][j] = palin[i + 1][j - 1]
            else:
                palin[i][j] = int(s[i] == s[j] and palin[i + 1][j - 1])
    for sz in range(n):
        for i in range(n - sz):
            j = i + sz
            if sz == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + palin[i][j]
    for _ in range(int(input())):
        (l, r) = list(map(int, input().split()))
        print(dp[l - 1][r - 1])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    for t in range(1):
        main()