Дівчинка Таня при допомозі гравців Test-the-Best все-таки змогла підрахувати, скільки їй знадобиться коробок, щоб виконати домашнє завдання. Але прийшов її молодший брат Петро і навіщось розклав деякі сірники у ряд на столі. Тепер Таня хочет його покарати - заставити зібрати сірнички назад у коробки. Дівчинка вона капризна і хоче, щоб брат зібрав не віе сірнички, а лише сірнички з номерами від \textbf{X} до \textbf{Y} включно (сірнички нумеруються зліва праворуч послідовними цілими числами, починаючи з нуля), а всі інші сірнички Таня попередньо зкине зі столу на підлогу (про реакцію тата на дії Тані в умові задачі замовчується :) ). Також Таня бажає накласти строгі умови на те, у якому порядку і скільки сірничків Петрик повинен брати зі столу. Умови ці звучать наступним чином: за один раз брат повинен взяти якомога більше сірничків, які лежать підряд, однакової довжини, причому серед них повинен бути сірничок з мінімальним номером. З якихось незрозумілих причин Таню цікавить, яку максимальну кількість сірничків за один раз візьме Петрик зі столу під час процесу збирання сірників. Підрахувати цю величину вона попросила вас. Так як зі значеннями \textbf{X} і \textbf{Y} Таня ще точно не визначилась, то зрбити підрахунки потрібно буде відразу для декількох пар (\textbf{X}, \textbf{Y}). \InputFile Перший рядок задає зліва праворуч довжини сірників, які лежать на столі. Кажен символ цього рядка - цифра '\textbf{1}'..'\textbf{9}', яка визначає довжину відповідного сірничка. Рядок містить від от \textbf{1} до \textbf{100000} символів включитно. Другий рядок містить відокремлений одиночними пропусками список пар (\textbf{X}, \textbf{Y}), для яких необхідно підрахувати величину, цікаву Тані. Кожна пара описується у вигляді "(\textbf{X}, \textbf{Y})". Рядок містить від \textbf{1} до \textbf{10000} пар. \OutputFile Знайти яку максимальну кількість сірничків брат Тані візьме за один раз зі столу для кожної з пар (\textbf{X}, \textbf{Y}), заданих у другому рядку. Порядок чисел у кінцевому рядку повинен відповідати порядку слідувануя пар у другому рядкуе, числа повинні бути відокремлені одиночними пропусками - див. приклад вихідних даних. \textbf{Пояснення до прикладів} \textit{Sample 1} У всіх 4-х випадках Петя зможе за один раз взяти зі столу всі сірнички. \textit{Sample 2} У всіх 4-х випадках Петя завжди буде за один раз брати зі столу по одному сірничку. \textit{Sample 3} \textit{1-й випадок: X=1, Y=5.} Перед Петриком залишаться сірнички \{2, 3, 3, 3, 4\}. Спочатку він візьме один сірник довжини 2, потім 3 сірнички довжини 3 і, нарешті, потім один сірник довжини 4. Максимальна кількість взятих за раз сірників - 3. \textit{2-й випадок: X=0, Y=13.} Перед Петриком залишаться всі сірнички. На 5-му кроці він візьме 4 сірнички довжини 2. \textit{3-й випадок: X=2, Y=7.} Перед Петриком залишаться сірнички \{3, 3, 3, 4, 2, 2\}. І, як вт вже напевно самі здогадались, спочатку він візьме 3 сірнички довжини 3, потім один сірник довжини 4 і в кінці 2 сірники, що залишились, довжини 2.