Problem J
Automatic Trading

A brokerage firm is interested in detecting automatic trading. They believe that a particular algorithm repeats itself; that is, it makes the same sequence of trades at a later time. The firm has identified a set of 26 key stocks that they believe are likely to be traded in concert, and they’ve encoded a series of trades as a string of letters: the letter itself indicates the stock, upper case indicates a buy, lower case indicates a sell. They want you to write a program to determine, for any two starting points, the longest sequence of identical trades from those two starting points, starting from and including those starting points as the first trade in the sequence.

Input

There will be a single test case in the input. This test case will start with a string $s$ on the first line, consisting solely of upper case and lower case letters ($1 \le \text {length}(s) \le 100\, 000$). On the next line will be an integer $q$ ($1 \le q \le 100\, 000$), indicating the number of queries. The following $q$ lines each describe a query with two integers, $i$ and $j$ ($0 \le i < j < \text {length}(s)$), which represent two zero-based positions in the string.

Output

For each query, output a single integer, indicating the length of the longest sequence of trades starting at $i$ which is identical to the sequence of trades starting at $j$.

ABABABcABABAbAbab
3
0 2
1 6
0 7

4
0
5

SheSellsSeashellsByTheSeaShore
4
8 22
1 20
8 25
0 1

3
4
1
0