CF1520E Arranging The Sheep

你正在玩一个名为“排列绵羊”的游戏。这个游戏的目标是让所有绵羊排成一行。游戏中的关卡由一个长度为 $n$ 的字符串描述，字符串只包含字符 '.'（空位）和 '*'（绵羊）。每一步，你可以将任意一只绵羊向左或向右移动一格，前提是目标位置存在且为空。只要所有绵羊之间没有空位，即所有绵羊连续排列，游戏就结束。 例如，如果 $n=6$，关卡字符串为 "\*\*.\*.."，则可能的游戏过程如下： - 第 $4$ 个位置的绵羊向右移动，关卡状态变为 "\*\*..\*."； - 第 $2$ 个位置的绵羊向右移动，关卡状态变为 "\*.\*.\*."； - 第 $1$ 个位置的绵羊向右移动，关卡状态变为 ".\*\*.\*."； - 第 $3$ 个位置的绵羊向右移动，关卡状态变为 ".\*.\*\*."； - 第 $2$ 个位置的绵羊向右移动，关卡状态变为 "..\*\*\*."； - 所有绵羊已经排成一行，游戏结束。 对于给定的关卡，请你计算完成该关卡所需的最少移动次数。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来每个测试用例包含两行： 第一行包含一个整数 $n$（$1 \le n \le 10^6$）。 第二行包含一个长度为 $n$ 的字符串，仅由字符 '.' 和 '*' 组成，表示关卡的描述。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出完成该关卡所需的最少移动次数。

由 ChatGPT 4.1 翻译