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

We say that a string $t$ is 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.

Examples

Input 1

4
abca

Output 1

14