G. LaVI-Bavellabion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

我们称一个字符串 $$$S$$$ 与自然数 $$$q$$$ 构成的对 $$$(S,q)$$$ 是好的当且仅当下列条件满足：

  • $$$0 \leq q \lt |S|$$$，其中 $$$|S|$$$ 表示字符串 $$$S$$$ 的长度。
  • 如果执行 $$$q$$$ 次：将 $$$S$$$ 中开头的字符移动至末尾。那么最终得到字符串是回文串。

我们称一个字符串 $$$S$$$ 的价值为能与其构成好的对 $$$q$$$ 的数量。

现在给你一个仅由小写字母构成的长度为 $$$n$$$ 的字符串 $$$S$$$，请你求出它所有子串的价值之和。

Input

第一行，一个整数 $$$n$$$ 表示字符串的长度。

第二行，一个字符串 $$$S$$$。

Output

一行，一个整数，表示好对的数量。

Example
Input
10
abbaaacbbb
Output
39
Note

对于所有测试点，满足 $$$1 \leq n \leq 2 \times 10^5, s_i \in \{a,b,c,...,z\}$$$。