CF245H Queries for Number of Palindromes

You've got a string $ s=s_{1}s_{2}...\ s_{|s|} $ of length $ |s| $ , consisting of lowercase English letters. There also are $ q $ queries, each query is described by two integers $ l_{i},r_{i} $ $ (1

The first line contains string $ s $ $ (1

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.

Consider the fourth query in the first test case. String $ s[4...\ 6] $ = «aba». Its palindrome substrings are: «a», «b», «a», «aba».