Substring Contribution Query

Given a string (a), you are asked to answer several queries. In each query, you are given an interval substring of (a) and you need to process its characters one by one in a chosen order. The process is defined as follows:

1. You maintain a set (S) (initially empty) and a value (rp = 0).
2. In each step, choose a character (x) from the current substring and remove it. Then perform the following actions:
   • If (S) is empty, update (rp \mathrel{-}= 1).
   • Otherwise, if there exists an element in (S) that is (\ge x) (i.e. not smaller than (x)), update (rp \mathrel{-}= 1) and clear (S).
   • Finally, insert (x) into (S).
3. Repeat until the substring is empty.

You can choose the order in which the characters are processed. Your task is, for each query, to determine the maximum possible final value of (rp) (note that (rp) starts at 0).

Observation: In order to avoid a penalty during a step, when (S) is non-empty, you must choose (x) that is larger than every element currently in (S). Thus, you can avoid additional penalties by processing the characters in a strictly increasing order. Since duplicates cannot be placed in the same strictly increasing subsequence, the minimal number of processing groups equals the maximum frequency of any character in the substring. Therefore, the maximum final (rp) is (-m), where (m) is the maximum frequency of any single character in the substring.

Formally, if for a given substring the maximum frequency is (m), then the answer is: [ rp_{max} = -m. ]

inputFormat

The first line contains the string (a) consisting of lowercase letters. The second line contains an integer (q) representing the number of queries. Each of the following (q) lines contains two integers (l) and (r) (1-indexed), indicating the substring (a[l\ldots r]) to be processed.

outputFormat

For each query, output a single integer, the maximum possible final value of (rp) (which will be negative). Each answer should be printed on a new line.

sample

aba
3
1 1
1 2
1 3

-1
-1
-2