• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

متاسفانه باخبر شدیم که آقای مالیاتچی، به کشور فلان فرار مالیاتی کرده است!

حیف که دیر فهمیدیم وگرنه زودتر فرد مناسبی را جایگزین او می‌کردیم. از این رو این سوال شسته و رفته خدمت شما:

به یک رشته خوب می‌گوییم اگر حرفی در آن وجود داشته باشد که حداقل به اندازه‌ی نصف طول آن رشته آمده باشد. برای مثال رشته‌ی $ab$ خوب است در حالی که رشته‌ی $abc$ خوب نیست. حال به شما یک رشته می‌دهیم و شما باید تعداد زیررشته‌های خوب آن را خروجی دهید.

ورودی

در تنها سطر ورودی یک رشته که تنها از حروف کوچک انگلیسی درست شده است آمده است. طول این رشته بین ۱ تا $10^5$ می‌باشد.

خروجی

در تنها سطر خروجی تعداد زیررشته‌های خوب رشته‌ی ورودی را چاپ کنید.

مثال

ورودی نمونه ۱

aaa

خروجی نمونه ۱

6

ورودی نمونه ۲

z

خروجی نمونه ۲

1