Longest Palindrome Construction

You are given a string \(S\) and \(Q\) queries. For each query you are provided with two integers \(L\) and \(R\) (0-indexed) that define a substring \(S[L \ldots R]\). Your task is to determine the length of the longest palindrome that can be constructed by rearranging the characters of the substring.

A palindrome is a string that reads the same forwards and backwards. The key observation is that for each character, you can use the even part of its frequency, and if any character occurs with an odd frequency, you can place one occurrence in the middle of the palindrome. In mathematical terms, if a character appears \(f\) times, then you can add \(2 \times \lfloor f/2 \rfloor\) to the palindrome length and possibly add 1 more to the total length if any \(f\) is odd.

inputFormat

The input is given from standard input (stdin) and has the following format:

1. A single line containing the string \(S\) of length \(N\). The string consists of lowercase English letters.
2. A single line containing an integer \(Q\), representing the number of queries.
3. Each of the next \(Q\) lines contains two integers \(L\) and \(R\) separated by a space, representing the indices for the substring \(S[L \ldots R]\).

outputFormat

For each query, print one integer on a separate line, which is the length of the longest palindrome that can be constructed from the characters of the specified substring.

## sample

abacaba
3
0 6
1 5
2 4

7
5
3

</p>