C. Counting Strings
time limit per test
6.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ of length $$$n$$$.

We say that a string $$$t$$$ is $$$\bf{mentioned}$$$ in $$$s$$$ if and only if there exist integers $$$l,r$$$, satisfying $$$1 \le l \le r \le n$$$, $$$\gcd(l, r) = 1$$$ and $$$s[l, r] = t$$$.

Here, $$$s[l, r]$$$ is defined as the string that is made by concatenating $$$s_l, s_{l+1}, \dots, s_r$$$, and $$$\gcd(l, r)$$$ represents the greatest common divisor of $$$l$$$ and $$$r$$$.

You should calculate the sum of the lengths of all distinct non-empty strings that are mentioned in $$$s$$$.

Input

The first line of the input contains the integer $$$n$$$ ($$$1 \le n \le 100000$$$).

The second line contains the string $$$s$$$, consisting of only lowercase English letters.

Output

Print the sum of the lengths of all distinct non-empty strings that are mentioned on a single line.

Example
Input
4
abca
Output
14