Вы играете в игру «Упорядочивание овец». Цель этой игры — сделать так, чтобы овцы выстроились в ряд. Уровень в игре описывается строкой длины \(n\), состоящей из символов '.' (пустое пространство) и '*' (овечка). За один ход вы можете передвинуть любую овечку на одну клетку влево или на одну клетку вправо, если соответствующая клетка существует и пуста. Игра заканчивается, как только овцы выстроились в ряд, то есть между любыми овечками не должно быть пустых клеток.
Например, если \(n=6\) и уровень описывается строкой «**.*..», тогда возможен следующий сценарий игры:
- овечка на позиции \(4\) двигается вправо, состояние уровня: «**..*.»;
- овечка на позиции \(2\) двигается вправо, состояние уровня: «*.*.*.»;
- овечка на позиции \(1\) двигается вправо, состояние уровня: «.**.*.»;
- овечка на позиции \(3\) двигается вправо, состояние уровня: «.*.**.»;
- овечка на позиции \(2\) двигается вправо, состояние уровня: «..***.»;
- овцы выстроились в ряд, игра завершается.
Для заданного уровня определите минимальное количество ходов, которое нужно сделать, чтобы пройти уровень.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество ходов, которое нужно сделать, чтобы пройти уровень.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**
|
1
0
0
0
9
|