Hasarın təmiri

Köhnə bir hasarı təmir etməlisiniz. Hasar, bəziləri qırılmış olan bir sıra taxtalardan ibarətdir. Taxtalar soldan sağa doğru artan qaydada nömrələnib. $i$-dən $j$-ə qədər olan bütün taxtaların təmiri, burada $j$ $i$-dən böyük və ya bərabərdir, $\sqrt{j-i+1}$-ə başa gəlir. Ümumi təmir xərclərini azaltmaq üçün bəzən bütöv taxtaları da təmir etmək sərfəli ola bilər. Bütün hasarın təmirinin minimal dəyərini tapmaq lazımdır.

Sizə hasar haqqında məlumat verilib. Qırıq taxtalar "X" simvolları ilə, bütöv taxtalar isə "." simvolları ilə göstərilib. Bütün hasarın təmirinin ən az dəyərini tapın.

Giriş verilənləri

Hər bir sətir hasarı təsvir edən ayrı bir testdir. O yalnız "X" və "." simvollarını ehtiva edir. Hər bir hasarın uzunluğu $2500$ simvoldan çox deyil.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə bütün hasarın təmirinin ən az dəyərini $4$ onluq rəqəmlə çıxarın.

Nümunələr