Count Distinct Characters in Substrings

You are given a string s of length \(n\) and \(q\) queries. Each query provides two indices \(l\) and \(r\) (0-indexed). For every query, you need to count the number of distinct characters in the substring \(s[l \ldots r]\). This problem tests your ability to manipulate strings and use data structures to efficiently track unique characters.

For example, if \(s = \texttt{abacaba}\) and the query is \(l = 0, r = 3\), the substring is \(s[0 \ldots 3] = \texttt{abac}\) which contains 3 distinct characters: a, b, and c.

inputFormat

The input is read from stdin and consists of the following:

1. An integer \(n\) denoting the length of the string.
2. A string s of length \(n\).
3. An integer \(q\) representing the number of queries.
4. For each of the next \(q\) lines, two integers \(l\) and \(r\) denoting the start and end indices of a query.

outputFormat

For each query, output a single integer on a new line representing the count of distinct characters in the substring \(s[l \ldots r]\).

## sample

7
abacaba
1
0 3

3

</p>