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

Обмеження: 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.