文字列に対する「折りたたみ」という操作を定義します。折りたたみは、何回か（0 回でもかまいません）の折る操作からなります。それぞれの折る操作では、隣り合う 2 文字の間で折り、文字列の後半部分（文字列の先頭から遠い側）を前半部分（文字列の先頭に近い側）の上に、逆向きにして、折り目の位置をそろえて重ねます。この操作によって、文字列は、行った折る操作の回数よりも層が 1 つ多い構造に変換されます。

折りたたみ後の文字列は、文字を重ねた山がいくつか並んだものと見なせます。同じ山にある文字がすべて等しいとき、その折りたたみは有効であるといいます。

折りたたみの対応する集合とは、元の文字列において各折り目の直前にある文字の位置の集合です。例えば、2 文字目と 3 文字目の間で 1 回だけ折った折りたたみの対応する集合は $\{2\}$ であり、0 回折った折りたたみの対応する集合は空集合です。2 つの折りたたみは、その対応する集合が等しいとき、かつそのときに限り、同じと見なします。

整数 $a,b$ ($0 \le b < a$) を選んで、$x \in S \iff 1 \le x < n,\ x \equiv b \pmod a$ とできるとき、集合 $S$ は等差的であるといいます。ここで $n$ は文字列の長さです。例えば $n=10$ の場合、集合 $\varnothing$、$\{2\}$、$\{1,9\}$、$\{2,4,6,8\}$ は等差的ですが、集合 $\{1,2,4\}$、$\{1,5\}$、$\{7,8,9\}$ は等差的ではありません。

有効であり、かつ対応する集合が等差的である折りたたみを素晴らしいといいます。理解の助けとして、次のページの図を参照してください。

文字列が与えられます。与えられた文字列の素晴らしい折りたたみの個数を数えてください。

入力

唯一の行に、ラテン文字、数字、アンダースコア、ハイフンからなる長さ $n$ ($1 \le n \le 10^6$) の文字列が与えられます。

出力

与えられた文字列の素晴らしい折りたたみの個数を、1 つの整数として出力してください。

入出力例

入力 1

aaaaa

出力 1

9

入力 2

V-oo-V

出力 2

2

入力 3

gritukan

出力 3

1

入力 4

Lhic

出力 4

1

入力 5

OO0OOO00O0OOOO0O00OOO0OO

出力 5

6

入力 6

SpyCheessee

出力 6

3

入力 7

Aa

出力 7

1

入力 8

228322

出力 8

4

入力 9

______________________________________

出力 9

380

注記

最初の例の素晴らしい折りたたみの対応する集合は、$\varnothing$、$\{1\}$、$\{2\}$、$\{3\}$、$\{4\}$、$\{1,3\}$、$\{1,4\}$、$\{2,4\}$、$\{1,2,3,4\}$ です。

これは文字列 `aabccbaa` の素晴らしい折りたたみです。対応する集合は $\{1,4,7\}$ です。

これは文字列 `abc` の素晴らしい折りたたみです。対応する集合は $\varnothing$ です。

これは有効な折りたたみではありませんが、折りたたみであり、対応する集合は等差的です。対応する集合は $\{2,6,10\}$ です。

上側の部分が下側と同じ向きに進んでいるので、これは折りたたみではありません。

上側の部分が同じ向きに進んでいる（右向きに進むと考えた場合）か、位置がそろっていない（左向きに進むと考えた場合）ので、これは折りたたみではありません。

これは有効な折りたたみですが、対応する集合は等差的ではありません。対応する集合は $\{4,6\}$ です。

そして、これが TeX の使い方です。