Unique Character Count in Substrings

You are given a string s and a number of queries. Each query contains a pair of indices i and j. For each query, your task is to compute the number of unique characters in the substring \(s[i\ldots j]\) (i.e. from the index i to j inclusive).

Input Constraints:

• The string s may contain lowercase or uppercase letters.
• Queries are given as pairs of integers with 0-based indexing.

Example:

Input:
abacaba
3
0 3
1 4
2 6
Output:
3 3 3

</p>

In the above example, the unique character counts for the substrings s[0...3], s[1...4], and s[2...6] are 3, 3, and 3 respectively.

inputFormat

The first line contains the string s.

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

The following q lines each contain two integers i and j separated by a space.

You should read input from standard input (stdin).

outputFormat

Output a single line with q integers separated by spaces. Each integer is the count of unique characters in the substring s[i...j] for the corresponding query.

Output the result to standard output (stdout).

## sample

abacaba
3
0 3
1 4
2 6

3 3 3