Longest Palindromic Substring Query

You are given a string s and q queries. Each query is represented by two 1-indexed integers l and r indicating a substring of s from the l-th character to the r-th character (inclusive). For each query, determine the length of the longest palindromic substring within the specified substring.

A palindrome is a string that reads the same backward as forward. For example, in the string "abaxyzbamadam", if we take the substring from the 1st to the 13th character, the longest palindromic substring is of length \(5\) (e.g. "madam").

Note: The indices are 1-indexed. You are expected to use an algorithm that checks all possible substrings in the queried range to determine the longest palindromic substring.

inputFormat

The first line contains a string s (without spaces).

The second line contains an integer q, the number of queries.

The following q lines each contain two integers l and r separated by a space, representing a query.

outputFormat

For each query, output the length of the longest palindromic substring in the specified substring on a separate line.

## sample

abaxyzbamadam
3
1 5
6 10
1 13

3
3
5

</p>