Мы определяем значение юмора строки $$$t$$$ как длину самой длинной палиндромной строки, которая встречается в ней как минимум дважды.

Формально, строка $$$p$$$ является юмором относительно $$$t$$$, если и только если выполняются оба следующих условия:

1. $$$p$$$ является палиндромом, и
2. существуют как минимум два различных индекса $$$i \in [1, |t| - |p| + 1]$$$, такие что $$$t[i, i + |p| - 1] = p$$$.

Значение юмора строки $$$t$$$ определяется как максимальная длина среди всех юморных строк относительно $$$t$$$.

Вам дана строка $$$s$$$ длины $$$n$$$, которая содержит только строчные латинские буквы, и $$$q$$$ запросов. Каждый запрос содержит два целых числа $$$l_i$$$, $$$r_i$$$, и вам нужно найти значение юмора строки $$$s[l_i, r_i]$$$.

Здесь $$$a[l, r]$$$ определяется как строка $$$a_l,a_{l+1},\ldots,a_r$$$.