Palindromes and Queries 2

You are given a string $S$ of lowercase letters. Write a program that processes the following queries in order.

• index len: print the number of palindromic substrings of $S$ that start at character index and have length at least len.

A palindrome is a string that reads the same forward and backward. The string of length 0 is also a palindrome, so when len is 0 the substring of length 0 starting at index counts as one more palindrome.

The first line contains the string $S$. Its length is at most 100,000, and it consists only of lowercase English letters.

The second line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

Each of the next $M$ lines contains one query, given as two integers index and len ($0 \le index < |S|$, $0 \le len \le 100{,}000$).

String indices start at 0.

Print the answer to each query on its own line, in the order the queries are given.