In this challenge, a string and a list of intervals are given. The string consists of English letters only and it can contain both lowercase and uppercase letters.

For two different letters, we say that the first letter is greater than the second letter when the first letter comes later in the alphabet than the second letter ignoring the case of the letters. For example, the letter 'Z' and 't' are greater than the letters 'b' and 'G', while the letters 'B' andd 'b' are equal as case is not considered.

The task is the following. For each given interval, you need to find the count of the greatest letter occurring in the string in that interval, ignoring the case of the letters, so occurrences of, for example, and are occurrences of the same letter.

Consider, for example, for the string "AbaBacD". In the interval, [0, 4], the greatest letter is 'b' with count 2.

Input Format

The first line contains integer , denoting the length of the input string.

The second line contains string .

The third line contains an integer , denoting the number of intervals. Each line of the subsequent lines contains two space-separated integers and , denoting the beginning and the end of interval.

Constraints

Subtasks

For of the maximum score.

Output Format

For each interval, print the count of the greatest letter occurring in the string in that interval.

Sample Input 0

5
ddaaa
1
0 4

Sample Output 0

2

Explanation 0

The string is "ddaaa" and there is only one interval, i.e. the interval denoting the whole string. The greatest character occuring in that interval is and its count is , therefore, is the answer.

Sample Input 1

8
aAabBcba
5
2 6
1 2
2 2
0 4
0 7

Sample Output 1

1
2
1
2
1

Explanation 1

The input string is "aAabBcba" and there are 5 intervals to check:

  1. -> aA[abBcb]a -> '' is the greatest and occurs time
  2. -> a[Aa]bBcba -> '' is the greatest and occurs times
  3. -> aA[a]bBcba -> '' is the greatest and occurs time
  4. -> [aAabB]cba -> '' is the greatest and occurs times
  5. -> [aAabBcba] -> '' is the greatest and occurs time
Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score