Девочка Таня с помощью игроков 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.