Подвійне повторення

Обмеження: 3 сек., 512 МіБ

Зеник знає, що Марічці подобаються рядки, які є подвійним повторенням однієї і тієї ж послідовності символів. Формально, рядок $t$ довжини $2 \cdot k$ вважаємо таким, що повторюється двічі, якщо для кожного $0 \le i < k$ виконується $t[i] = t[i + k]$. Наприклад, рядок aabaab є подвійним повторенням рядка aab, а от рядок ababab не є рядком що повторюється двічі.

Одного разу, прямуючи до Коледжу алгоритмічного програмування, Зеник натрапив на рядок $s$ довжини $n$. Він вирішив видалити $l$ символів із початку рядка та $r$ символів із кінця, а все, що залишиться, подарувати Марічці. Важливо, щоб залишений рядок мав хоча б один символ, тобто, формально, $l + r < n$. При цьому $l$ та/або $r$ можуть бути рівними нулю.

Допоможіть Зенику визначити кількість пар $(l, r)$, які він може вибрати так, щоб подарувати Марічці рядок із подвійним повторенням.

Вхідні дані

У першому рядку задано одне ціле число $n$ — довжину рядка, що знайшов Зеник.

У наступному рядку задано $s$ — рядок, який знайшов Зеник.

Вихідні дані

У єдиному рядку виведіть одне ціле число — кількість пар $(l, r)$, що після видалення $l$ символів з початку та $r$ символів з кінця утвориться рядок, який є подвійним повторенням однієї і тієї ж послідовності символів.

Обмеження

$1 \le n \le 10^4$,

рядок $s$ містить лише маленькі англійські букви.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 abcababcabc	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 aabaab	3

Примітки

У першому прикладі Зеник може обрати такі пари $(l, r)$:

• пара (3, 4) залишить вкінці рядок abab,

• пара (0, 1) залишить abcababcab,

• пара (5, 0) залишить abcabc.

У другому прикладі Зеник може обрати такі пари $(l, r)$:

• пара (0, 0) залишить вкінці увесь рядок aabaab,

• пара (0, 4) залишить aa,

• пара (3, 1) залишить aa.