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

Limits: 3 sec., 512 MiB

Зеник знає, що Марічці подобаються рядки, які є подвійним повторенням однієї і тієї ж послідовності символів. Формально, рядок \(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)\), які він може вибрати так, щоб подарувати Марічці рядок із подвійним повторенням.

Input

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

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

Output

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

Constraints

\(1 \le n \le 10^4\),

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

Samples

Input (stdin) сopy	Output (stdout) сopy
11 abcababcabc	3

Input (stdin) сopy	Output (stdout) сopy
6 aabaab	3

Notes

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

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

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

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

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

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

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

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