I am stuck on this following problem:

Statement:

Given a string of size n and q queries of type (l,r) you need to find how many palindromes are there in the substring of range [l...r].

Constraints:

1<=n,q<=100000

1<=l<=r<=n

Thanks for reading the problem. It will be really helpful if you can give me a solution.