Matchbox#1435

Matchbox

4 seconds

64 megabytes

Medium

Girl Tanya, with the help of Test-the-Best players, managed to calculate how many boxes she needed to complete her homework. But then her younger brother Petya came and for some reason laid out some of the matches in a row on the table. Now Tanya wants to punish him — to make him put the matches back into the boxes. She is a capricious girl and wants her brother to collect not all the matches, but only the matches with numbers from $X$ to $Y$ inclusive (matches are numbered from left to right with consecutive integers starting from zero), and all the other matches Tanya will throw off the table onto the floor in advance (the reaction of their father to Tanya's actions is not specified in the statement :) ).

Tanya also wants to impose strict conditions on the order and quantity of matches Petya must take from the table. These conditions are as follows: at one time, the brother must take as many consecutive matches of the same length as possible, and among them must be the match with the minimal number.

For some unclear reason, Tanya is interested in the maximum number of matches Petya will take from the table at one time during the process of collecting matches. She asked you to calculate this number. Since Tanya hasn't fully decided on the values of $X$ and $Y$ , calculations must be made immediately for several pairs $(X, Y)$ (X, Y).

Input

The first line gives from left to right the lengths of the matches lying on the table. Each character in this line is a digit '1'..'9', determining the length of the corresponding match. The line contains from $1$ to $100000$ characters inclusive.

The second line contains a list of pairs $(X, Y)$ (X, Y) separated by single spaces, for each of which the value of interest to Tanya needs to be calculated. Each pair is described as "(X, Y)". The line contains from $1$ to $10000$ pairs.

Output

For each pair $(X, Y)$ (X, Y) given in the second line, find the maximum number of matches that Tanya's brother will take from the table at one time. The order of the numbers in the output line should correspond to the order of the pairs in the second line, numbers should be separated by single spaces — see the sample output for reference.

Examples

Example 1

Note

Sample 1

In all $4$ cases, Petya can take all the matches from the table at once.

Sample 2

In all $4$ cases, Petya will always take one match from the table at a time.

Sample 3

1st case: $X = 1, Y = 5$ X = 1, Y = 5. Petya will have matches ${2, 3, 3, 3, 4}$ \{2, 3, 3, 3, 4\} left. First he will take one match of length $2$ , then $3$ matches of length $3$ , and finally one match of length $4$ . The maximum number of matches taken at once — $3$ .

2nd case: $X = 0, Y = 13$ X = 0, Y = 13. All matches remain. On the $5$ th step, he will take $4$ matches of length $2$ .

3rd case: $X = 2, Y = 7$ X = 2, Y = 7. The matches remaining are ${3, 3, 3, 4, 2, 2}$ \{3, 3, 3, 4, 2, 2\}. As you have probably guessed, he will first take $3$ matches of length $3$ , then one match of length $4$ , and finally the remaining $2$ matches of length $2$ .