Count Distinct Characters in Substrings

You are given a string S and Q queries. Each query consists of two integers l and r (1-indexed) representing the bounds of a substring. For each query, you need to compute and output the number of distinct characters in the substring S[l:r] (both ends inclusive).

Note: When processing the query, remember to convert the 1-indexed positions to 0-indexed positions if needed. For example, if S = "abacaba" and the query is (1, 3), the substring is "aba" and it contains 2 distinct characters: 'a' and 'b'.

The problem requires reading input from standard input (stdin) and printing the outputs to standard output (stdout).

inputFormat

The input consists of multiple lines:

• The first line contains the non-empty string S.
• The second line contains an integer Q representing the number of queries.
• The following Q lines each contain two space-separated integers l and r (1-indexed), denoting the bounds of the substring.

outputFormat

For each query, output a single integer on a new line representing the number of distinct characters in the substring S[l:r].

## sample

abacaba
1
1 3

2

</p>