Distinct Characters in Substrings

You are given a string S of length N and Q queries. In each query, you are provided with two integers L and R (1-indexed) representing the start and end indices of a substring. Your task is to determine the number of distinct characters present in the substring S[L...R].

Mathematically, for each query, compute the number of distinct characters in the substring \( S[L \ldots R] \).

inputFormat

The first line contains an integer N, the length of the string S.

The second line contains the string S consisting of uppercase letters.

The third line contains an integer Q, the number of queries.

Each of the next Q lines contains two space-separated integers L and R representing the indices of the substring.

outputFormat

For each query, output a single integer on a new line representing the number of distinct characters in the substring \( S[L \ldots R] \).

## sample

7
ABCADEA
3
1 3
2 5
4 7

3
4
3

</p>