Distinct Species in the Barn

You are given a string barn representing the species arranged in a barn, where each character denotes a species. You are also provided with a series of queries. Each query consists of two integers l and r (1-indexed), representing the starting and ending positions in the string. For each query, you are to determine the number of distinct species present in the substring barn[l...r].

For example, if barn = "abcabc" and the queries are (1, 3), (2, 5), and (1, 6), then the answer for each query is 3 because all three distinct species appear in these segments.

Input/Output Format

You need to read from standard input and write to standard output. The input begins with a line containing the string barn. The second line contains an integer q, the number of queries. This is followed by q lines, each containing two integers l and r separated by space. For each query, output the count of distinct species on a new line.

Note: All formulas or any mathematical notations (if needed) should be written in LaTeX format.

inputFormat

The first line contains a non-empty string barn that represents different species by lowercase English letters. 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 ( $1 \leq l \leq r \leq |barn|$), representing a query for the substring from index l to r (inclusive).

outputFormat

For each query, output a single integer on a new line representing the count of distinct species (i.e. distinct characters) in the corresponding substring of barn.

## sample

abcabc
3
1 3
2 5
1 6

3
3
3

</p>