Longest Palindromic Substring in a Range

Given a string (S) and a number of queries, each query contains two integers (l) and (r) which denote the starting index (inclusive) and ending index (exclusive) of a substring of (S). Your task is to compute, for each query, the length of the longest palindromic substring within the specified range.

A substring is a contiguous segment of a string. A palindrome is a string that reads the same backward as forward. Formally, for a query, you need to find the maximum integer (k) such that there exists an index (i) with (l \leq i) and a substring (S[i..j]) (with (j+1 \leq r)) which is a palindrome and (j - i + 1 = k).

inputFormat

The first line of input contains an integer (T) (the number of test cases). For each test case, the first line contains the string (S). The next line contains an integer (Q), the number of queries. This is followed by (Q) lines, each containing two integers (l) and (r) separated by a space, representing the range ([l, r)) of the substring in (S) to consider.

Note: It is guaranteed that (0 \le l < r \leq |S|), where (|S|) is the length of the string.

outputFormat

For each query, output a single line containing the length of the longest palindromic substring within the corresponding substring of (S). The outputs for all queries of all test cases should be printed in order, each on a new line.## sample

3
abaxyzzyxf
3
0 3
3 9
0 10
racecarannakayak
2
0 7
11 16
abb
2
0 1
1 3

3
6
6
7
5
1
2