Distinct Characters Query

You are given a string s of length n and q queries. Each query consists of two integers l and r denoting a 1-indexed range in the string. For each query, your task is to compute the number of distinct characters in the substring s[l...r].

In mathematical terms, given a query with indices \( l \) and \( r \), you need to compute: \[ distinct(s, l, r) = |\{ s_i : l \leq i \leq r \}| \] where \(|\cdot|\) denotes the cardinality of the set.

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The input starts with an integer n representing the length of the string.

The next line contains the string s.

The third line contains an integer q representing the number of queries.

Each of the next q lines contains two space-separated integers l and r (1-indexed) representing a query.

outputFormat

For each query, output a single line containing the number of distinct characters in the substring from index l to r of the string s.

## sample

11
abracadabra
3
1 10
2 4
6 9

5
3
3

</p>