長さ $n$ の文字列 $s$ が与えられる。
文字列 $t$ が $s$ において「言及されている (mentioned)」とは、$1 \le l \le r \le n$ かつ $\gcd(l, r) = 1$ を満たす整数 $l, r$ が存在し、$s[l, r] = t$ となることである。
ここで、$s[l, r]$ は $s_l, s_{l+1}, \dots, s_r$ を連結して作られる文字列と定義され、$\gcd(l, r)$ は $l$ と $r$ の最大公約数を表す。
$s$ において言及されているすべての異なる空でない文字列の長さの総和を計算せよ。
入力
入力の最初の行には整数 $n$ ($1 \le n \le 100000$) が含まれる。 2行目には、小文字の英字のみからなる文字列 $s$ が含まれる。
出力
$s$ において言及されているすべての異なる空でない文字列の長さの総和を1行で出力せよ。
入出力例
入出力例 1
4 abca
14