Longest Unique Substring Query

Given a string S consisting of lowercase English letters, and Q queries, each query consisting of two integers L and R, your task is to determine the length of the longest substring within the segment S[L..R] (1-indexed) that contains all unique characters.

The problem can be formulated mathematically as follows:

For a segment \( s = S[L..R] \), find the maximum \( k \) such that there exists an index \( i \) with \( 1 \leq i \leq R - L + 2 - k \) satisfying \[ \text{all characters in } s[i..i+k-1] \text{ are distinct.} \]

For example, if S = "aabbcdee" and the query is (1,8), the answer is 4, corresponding to the substring "bcde".

inputFormat

The first line of input contains the string S.

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

Each of the next Q lines contains two space-separated integers L and R representing the bounds of the query (1-indexed).

outputFormat

For each query, output the length of the longest substring with all distinct characters within S[L..R]. Each answer should be printed in a new line.

## sample

aabbcdee
3
1 4
2 7
1 8

2
4
4

</p>