Автоматическая торговля

Брокерская фирма заинтересована в выявлении автоматической торговли. Они подозревают, что определенный алгоритм повторяет последовательность сделок, то есть выполняет ту же последовательность в более позднее время. Фирма выделила набор из 26 ключевых акций, которые, по их мнению, вероятно, торгуются вместе, и закодировала серию сделок в виде строки букв: заглавная буква обозначает покупку, а строчная — продажу. Они хотят, чтобы вы разработали программу, которая определяет для любых двух начальных точек самую длинную последовательность идентичных сделок, начиная с этих точек, включая их как первую сделку в последовательности.

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

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

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

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