Maximum Character Frequency in Substrings

You are given a string s of length n and q queries. Each query contains two integers, l and r (0-indexed), which represent the bounds of a substring of s. For each query, determine the maximum frequency of any character within the substring s[l...r]. In mathematical terms, for each query, find

\( \max_{c \in \Sigma} \text{freq}(c) \)

where \( \text{freq}(c) \) denotes the number of times character \( c \) appears in the substring.

Print the result for each query on a separate line.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n representing the length of the string.
• The second line contains the string s.
• The third line contains an integer q representing the number of queries.
• The next q lines each contain two integers, l and r, separated by a space indicating the starting and ending indices (inclusive) of the substring.

outputFormat

For each query, output the maximum frequency of any character in the specified substring s[l...r]. Each result should be printed on a new line to stdout.

## sample

5
aabbc
2
0 2
1 4

2
2

</p>