G. Kozak Vus və sətirlər

Kozak Vus son zamanlar maraqlı bir problemə rast gəldi.

Bir sıra $s$ verilmişdir. Bu sıranın aşağıdakı xüsusiyyətlərə malik alt sıracıklarının sayını tapmaq lazımdır:

1. Alt sıracık ən azı $3$ hərfdən ibarət olmalıdır;

2. Alt sıracığın bütün hərfləri eyni olmalıdır, yalnız biri istisna olmaqla.

Məsələn, aab və cccdc sıracıkları bu xüsusiyyətlərə uyğundur, lakin ab, ccc və aabbaa sıracıkları uyğun deyil.

Bir sıra $x$, $y$ sıracığının alt sıracığıdır, əgər $x$ başlanğıcdan bir neçə (bəlkə də heç biri və ya hamısı) simvolu və sondan bir neçə (bəlkə də heç biri və ya hamısı) simvolu silməklə əldə edilə bilərsə.

Kozak Vusa bu məsələni həll etməkdə kömək edin.

Giriş verilənləri

Birinci sıracıq $s$ ($1\le |s|\le 2\cdot 10^5$) kiçik hərflərdən ibarət latın əlifbasından ibarətdir.

Çıxış verilənləri

Tək bir ədəd çıxarın — verilmiş şərtlərə uyğun alt sıracıkların sayı.

Nümunələr

Qiymətləndirmə

Əgər həll $|s|\le 100$ üçün düzgün işləyirsə, o, ən azı $15$ bal ilə qiymətləndiriləcək.

Əgər həll $|s|\le 5000$ üçün düzgün işləyirsə, o, ən azı $40$ bal ilə qiymətləndiriləcək.