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