Упаковка спичек

Девочка Таня с помощью игроков Test-the-Best все-таки смогла подсчитать, сколько ей понадобится коробков, чтобы выполнить домашнее задание. Но пришел ее младший брат Петя и зачем-то разложил некоторые спички в ряд на столе. Теперь Таня хочет его наказать - заставить собрать спички обратно в коробки. Девочка она капризная и хочет, чтобы брат собрал не все спички, а только спички с номерами от X до Y включительно (спички нумеруются слева направо последовательными целыми числами, начиная с нуля), а все остальные спички Таня предварительно сбросит со стола на пол (о реакции папы на действия Тани условие задачи умалчивает :) ).

Также Таня хочет наложить строгие условия на то, в каком порядке и сколько спичек Петя должен брать со стола. Условия эти звучат следующим образом: за один раз брат должен взять как можно больше лежащих подряд спичек одинаковой длины, причем среди них должна быть спичка с минимальным номером.

По каким-то непонятным причинам Таню интересует, какое максимальное количество спичек за один раз возьмет Петя со стола во время процесса сбора спичек. Подсчитать эту величину она попросила вас. Так как со значениями X и Y Таня еще окончательно не определилась, то произвести подсчеты необходимо будет сразу для нескольких пар (X, Y).

Входные данные

Первая строка задает слева направо длины спичек, лежащих на столе. Каждый символ этой строки - цифра '1'..'9', определяющая длину соответствующей спички. Cтрока содержит от 1 до 100000 символов включительно.

Вторая строка содержит разделенный одиночными пробелами список пар (X, Y), для которых необходимо подсчитать величину, интересную Тане. Каждая пара описывается в виде "(X, Y)". Строка содержит от 1 до 10000 пар.

Выходные данные

Найти какое максимальное количество спичек брат Тани возьмет за один раз со стола для каждой из пар (X, Y), заданных во второй строке. Порядок чисел в результирующей строке должен соответствовать порядку следования пар во второй строке, числа должны быть разделены одиночными пробелами - см. пример выходных данных.

Примеры

Примечание

Sample 1

Во всех 4-х случаях Петя сможет за один раз взять со стола все спички.

Sample 2

Во всех 4-х случаях Петя всегда будет за один раз брать со стола по одной спичке.

Sample 3

1-й случай: X=1, Y=5. Перед Петей останутся спички {2, 3, 3, 3, 4}. Сначала он возьмет одну спичку длины 2, затем 3 спички длины 3 и, наконец, потом одну спичку длины 4. Максимальное количество взятых за раз спичек - 3.

2-й случай: X=0, Y=13. Перед Петей останутся все спички. На 5-м шаге он возьмет 4 спички длины 2.

3-й случай: X=2, Y=7. Перед Петей останутся спички {3, 3, 3, 4, 2, 2}. И, как вы уже наверно сами догадались, вначале он возьмет 3 спички длины 3, затем одну спичку длины 4 и в конце 2 оставшиеся спички длины 2.