Distinct Characters Query

You are given a string S and an integer Q representing the number of queries. For each query, you are provided with two integers L and R (1-indexed) which define a substring of S (from position L to R, inclusive).

Your task is to determine the number of distinct characters in the specified substring and output the result for each query. Formally, if \(S\) is the input string, for every query \((L, R)\) you need to compute \(\lvert \{ S[i] : L \leq i \leq R \} \rvert\).

The input is read from standard input and the output is written to standard output. Each answer should be printed on a new line.

inputFormat

The first line contains the string S.

The second line contains an integer Q representing the number of queries.

Each of the next Q lines contains two space-separated integers L and R, indicating the starting and ending indices (1-indexed) of the substring.

Note: The indices are 1-indexed.

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

abacc
3
1 3
2 4
1 5

2
3
3

</p>