Longest Palindrome Query

You are given a string T of length M and Q queries. Each query is represented by two integers l and r, meaning that you need to consider the substring T[l-1:r] (using 1-indexed positions). Your task is to determine the length of the longest palindrome that can be formed by any permutation of the characters of the given substring.

A palindrome is a string that reads the same forward and backward. The trick here is to use the characters from the substring to form a palindrome by rearranging them. Formally, if you count the frequency of each character in the substring and let these frequencies be \(f_1, f_2, \dots, f_k\), then you can use all even counts entirely and for odd counts you can take \(f_i - 1\) (which is even) and add one extra character (if any odd frequency exists) in the middle. Thus, the maximum palindrome length is:

[ L = \sum_{i=1}^{k} (f_i - (f_i \mod 2)) + \min(1, #{i : f_i \text{ is odd}}) ]

Use the input data to answer all queries and output the result for each on a new line.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

M
T
Q
l1 r1
l2 r2
... 
 lQ rQ

Here, M is an integer representing the length of the string T (which you may or may not need to use explicitly), T is the string, Q is the number of queries, and each of the following Q lines contains two space-separated integers l and r representing a query.

outputFormat

For each query, output the length of the longest palindrome that can be formed from the characters of the substring T[l-1:r]. Each result should be printed on a separate line to standard output (stdout).

## sample

7
abccbaa
2
1 4
3 7

3
5

</p>