Задана строка 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.
Выходные данные
Выведите q целых чисел — ответы на запросы. Ответы на запросы выводите в том порядке, в котором запросы заданы во входных данных. Выведенные числа разделяйте пробельными символами.
Примечание
Рассмотрим четвертый запрос в первом тестовом примере. Строка s[4... 6] = «aba». Ее подстроки, являющиеся палиндромами: «a», «b», «a», «aba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
caaaba
5
1 1
1 4
2 3
4 6
4 5
|
1
7
3
4
2
|