C. Разбиение на палиндромы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Подстрокой называется непрерывный и непустой подотрезок букв из данной строки, без изменения порядка.

Чётным палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево, и имеет чётную длину. Например, строки «zz», «abba», «abccba» являются чётными палиндромами, а строки «codeforces», «reality», «aba», «c» не являются.

Красивой строкой называется чётный палиндром или строка, которую можно разбить на несколько меньших чётных палиндромов.

Дана строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв. Подсчитайте количество красивых подстрок в $$$s$$$.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Затем следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$. Строка $$$s$$$ состоит только из строчных латинских букв и имеет длину $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5\cdot 10^5$$$.

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

Для каждого набора входных данных выведите количество красивых подстрок.

Пример
Входные данные
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
Выходные данные
3
0
1
0
14
6
Примечание

В первом наборе входных данных красивыми подстроками являются «abaaba», «baab», «aa».

В последнем наборе входных данных красивыми подстроками являются «aa» (подсчитано дважды), «abba», «bb», «bbaa», «abbaaa».