Автоматична торгівля

Брокерська фірма зацікавлена у виявленні автоматичної торгівлі. Вони підозрюють, що певний алгоритм повторює однакову послідовність угод через деякий час. Фірма визначила набір з 26 ключових акцій, які, на їхню думку, можуть торгуватися разом, і закодувала серію угод у вигляді рядка літер: кожна літера представляє акцію, велика літера означає купівлю, а мала літера — продаж. Вони хочуть, щоб ви створили програму, яка визначить, для будь-яких двох початкових точок, найдовшу послідовність ідентичних угод, починаючи з цих двох точок, включаючи ці точки як першу угоду в послідовності.

Вхідні дані

Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок починається з рядка s на першому рядку, що складається виключно з великих і малих літер (1 ≤ довжина(s) ≤ 100000). На наступному рядку буде ціле число q (1 ≤ q ≤ 100000), що вказує на кількість запитів. Наступні q рядків описують кожен запит двома цілими числами, i та j (0 ≤ i < j < довжина(s)), які представляють дві позиції з нульовою базою в рядку. Вхідні дані закінчуються рядком, що містить лише зірочку ('*').

Вихідні дані

Для кожного запиту виведіть одне ціле число, що вказує на довжину найдовшої послідовності угод, починаючи з i, яка ідентична послідовності угод, починаючи з j. Виводьте без пробілів. Не друкуйте жодних порожніх рядків між рядками виводу.