H. Запросы на количество палиндромов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка s = s1s2... s|s| длины |s|, состоящая из строчных букв латинского алфавита. А также q запросов, каждый запрос описывается двумя целыми числами li, ri (1 ≤ li ≤ ri ≤ |s|). Ответ на запрос — количество подстрок строки s[li... ri], которые являются палиндромами.

Строка s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) называется подстрокой строки s = s1s2... s|s|.

Строка t называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Формально, если t = t1t2... t|t| = t|t|t|t| - 1... t1.

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

В первой строке записана строка s (1 ≤ |s| ≤ 5000). Во второй строке записано единственное целое число q (1 ≤ q ≤ 106) — количество запросов. В следующих q строках записаны сами запросы. В i-той из этих строк записаны два целых числа через пробел li, ri (1 ≤ li ≤ ri ≤ |s|) — описание i-того запроса.

Гарантируется, что заданная строка состоит только из строчных букв латинского алфавита.

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

Выведите q целых чисел — ответы на запросы. Ответы на запросы выводите в том порядке, в котором запросы заданы во входных данных. Выведенные числа разделяйте пробельными символами.

Примеры
Входные данные
caaaba
5
1 1
1 4
2 3
4 6
4 5
Выходные данные
1
7
3
4
2
Примечание

Рассмотрим четвертый запрос в первом тестовом примере. Строка s[4... 6] = «aba». Ее подстроки, являющиеся палиндромами: «a», «b», «a», «aba».