Given a string S,you are asked to find the longest palindrome in the substring [l,r].
The first line is a number T which indicates the number of test cases
then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].
the answer for each query.