Problem Description

Given a string S,you are asked to find the longest palindrome in the substring [l,r].

Input

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].

Output

the answer for each query.

1
aaabbcc
5
1 7
1 4
2 3
4 5
2 5

3
3
2
2
2

Hint

1 7 means aaabbcc the longest palindrome substring is aaa,whose length is 3.
4 5 means bb the longest palindrome substring is bb,whose length is 2.