Distinct Character Count in a Substring

Given a string (s) of length (n) consisting of lowercase English letters, and (q) queries, each query asking for the number of distinct characters in the substring of (s) within indices (l) to (r) (inclusive), your task is to compute and output the answer for each query.

For example, if (s = \texttt{abacaba}) and one query is (l = 0) and (r = 3), the substring is (\texttt{abac}) and the distinct characters are ({a, b, c}), so the answer is 3.

Note that indices are 0-based.

inputFormat

The input is read from standard input (stdin) and follows this format:

1. An integer (n), representing the length of the string (s).
2. A string (s) of length (n) (only lowercase English letters).
3. An integer (q), representing the number of queries.
4. (q) lines follow; each line contains two space-separated integers (l) and (r) (0-indexed) representing a query that asks for the number of distinct characters in the substring (s[l \ldots r]).

outputFormat

For each query, output a single line containing the number of distinct characters in the substring (s[l \ldots r]). The output is written to standard output (stdout).## sample

7
abacaba
2
0 3
2 5

3
3