Longest Non-Repeating Substring Queries

Given a string S and a series of queries, each query specifying two indices L and R, your task is to determine the length of the longest substring within the substring S[L...R] that does not contain any repeated characters.

Note: The indices are 1-indexed. For each query, consider the substring S[L...R] and compute the maximum length of a contiguous segment in that substring where each character appears at most once.

Example: For S = "abcabcbb" and query (1, 4), the substring is "abca". The longest substring without repeating characters is "abc", which has a length of 3.

inputFormat

The input is read from standard input. The first line contains an integer T, representing the number of test cases. Each test case is described as follows:

• A line containing the string S.
• A line containing an integer Q, the number of queries.
• Q subsequent lines, each containing two integers L and R separated by a space, representing a query.

It is guaranteed that 1 ≤ L ≤ R ≤ |S|, where |S| is the length of the string S.

outputFormat

For each test case, output a single line containing Q integers separated by a space. Each integer represents the length of the longest substring without repeating characters for the corresponding query.

## sample

1
abcabcbb
3
1 4
2 5
3 8

3 3 3

</p>