Distinct Characters in Substrings

You are given a string \(S\) and \(Q\) queries. Each query consists of two integers \(l\) and \(r\) (0-indexed), which represent the starting and ending indices of a substring of \(S\). Your task is to compute the number of distinct characters in each substring \(S[l \ldots r]\).

Note: The indices are 0-indexed and the substring includes both the characters at \(l\) and \(r\). Efficient handling of multiple queries is recommended.

Example:

Input:
abacabadab
3
0 3
1 4
2 7
Output:
3
3
4

</p>

inputFormat

The first line of input contains the string \(S\).

The second line contains an integer \(Q\), the number of queries.

Each of the following \(Q\) lines contains two space-separated integers \(l\) and \(r\) which denote the start and end indices of the substring.

outputFormat

For each query, output a single line containing the number of distinct characters in the substring \(S[l \ldots r]\).

## sample

abacabadab
3
0 3
1 4
2 7

3
3
4

</p>