Вам необхідно полагодити старий паркан. Паркан складається з набору дошок, деякі з яких виламані. Дошки пронумеровані зліва направо у зростаючому порядку. Полагодження усіх дошок від \(i\)-ої до \(j\)-ої включно, де \(j\) більше або дорівнює \(i\), коштує \(j−i+1\). Для зменшення загальної вартості ремонту іноді вигідно ремонтувати навіть цілі дошки. Необхідно знайти мінімальну вартість ремонту усього паркану.

Вам надано інформацію про паркан. Зламані дошки позначаються символами "X", а цілі символами ".". Знайти найменшу вартість полагодження усього паркану.

Вхідні дані

Кожний рядок є окремим тестом, що описує паркан. Він містить лише символи "X" та ".". Довжина кожного паркану не більша за 2500 символів.

Вихідні дані

Для кожного тесту в окремому рядку вивести найменшу вартість полагодження усього паркану з 4 десятковими цифрами.

Вхідні дані #1

X.X...X.X
X.X.....X
X.............XX.X.......X...X..

Відповідь #1

3.0000
2.7321
5.0000