平方連続部分文字列

古代国家イワシロでは、今年は雨がほとんど降らず、民衆は困っていました。そのため、新米神官のあなたが、リュウガサワで雨乞いの儀式をすることになりました。

雨乞いの儀式では、雨を降らせてくれる竜神様のために、祈りの書に書かれた祈りの呪文を唱えます。呪文を唱え終えると、竜神様はその呪文の中に、同じ言葉が２回続けて現れる個所がいくつあったか、あなたに尋ねます。あなたがそれを言い当てれば、祈りが成就して竜神様が雨を降らせてくれます。

たとえば、あなたがababababという呪文を唱えたら、その中に現れる同じ言葉が２回続けて現れる箇所は、以下の６箇所になります。

• １文字目から始まるababababの１箇所（ababが２回続けて現れる）。
• １文字目、３文字目、５文字目からそれぞれ始まるababの３箇所（abが２回続けて現れる）。
• ２文字目と４文字目からそれぞれ始まるbabaの２箇所（baが２回続けて現れる）。

祈りを成就させるためには、どんな呪文を唱えたときも、あなたはそのような箇所の個数を正確に答えなければなりません。

文字列が与えられたとき、その中に同じ文字列が２回続けて現れる箇所の個数を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$str$

１行に英小文字からなる文字列$str$が与えられる。ただし、$str$の長さは3以上100,000以下である。

出力

与えられた文字列の中に同じ文字列が２回続けて現れる箇所の個数を1行に出力する。

入出力例

入力例１

abababab

出力例１

6

入力例２

aaaaaaa

出力例２

12

Note

Algorithm

 

---