Count Distinct Characters in Substrings

You are given a string (s) consisting of lowercase English letters and (q) queries. Each query provides two indices (l) and (r) (with (0 \le l \le r < n)) that define a substring of (s). Your task is to compute the number of distinct characters in each substring (s[l \ldots r]).

For a given query, the answer is defined as: [\text{answer} = \left| { s[i] : l \le i \le r } \right|] where (|\cdot|) denotes the cardinality of the set.

This problem tests your ability to process strings and utilize appropriate data structures to count unique elements.

inputFormat

The first line contains the string (s). The second line contains an integer (q) denoting the number of queries. Each of the following (q) lines contains two space-separated integers (l) and (r), representing the left and right indices (inclusive) of a substring.

outputFormat

For each query, output a single line with an integer representing the number of distinct characters in the corresponding substring (s[l \ldots r]).## sample

abcba
3
0 1
1 4
1 1

2
3
1