Distinct Characters in Substrings

You are given a string \(s\) and \(Q\) queries. Each query contains two integers \(l\) and \(r\) (0-based indices) corresponding to the start and end indices of a substring of \(s\). Your task is to determine the number of distinct characters in the substring \(s[l:r+1]\). For example, if \(s = \texttt{abacaba}\) and the query is \([0, 3]\), then the substring is \(\texttt{abac}\) which contains the distinct characters \(a, b, c\), so the answer is 3.

Note: The indices are inclusive, and you should output the result for each query on a separate line.

inputFormat

The input is given via standard input (stdin) and has the following format:

Line 1: A non-empty string \(s\).
Line 2: An integer \(Q\), representing the number of queries.
Next \(Q\) lines: Each line contains two space-separated integers \(l\) and \(r\) (0-based indices), representing the start and end indices of a substring.

outputFormat

For each query, output one integer on a new line -- the number of distinct characters in the substring \(s[l:r+1]\).

## sample

abacaba
4
0 3
1 2
2 5
0 6

3
2
3
3

</p>