宝藏 1000ms/256mb

【问题描述】

小 A 得到了一堆宝藏，分散在一维的格子上，有些格子是空的，有些格子上有一个宝藏。

小 A 想要把宝藏一个接着一个都堆在最左侧，他想要请求你的帮助。

你可以站在一个空的格子里向左推或者向右拉宝藏。形如（.#人 -> #人.）（#人. -> .#人）

输出最小的操作次数或说明无解（输出 $-1$）。

【输出格式】

第一行一个 $T$，表示数据组数。

接下来 $2\times T$ 行每 $2$ 行表示一组数据：

每组数据第一行一个正整数 $N$ 表示格子的个数，接下来一行一个长度为 $N$ 的字符串，保证仅含有 # 和 .。

【输出格式】

$T$ 行，每行一个正整数表示答案

【输入样例】

8
6
###...
5
##.#.
8
#.#.#.#.
6
#.####
6
####.#
9
.##..#...
9
##.###...
13
..####.......

【输出样例】

0
1
6
-1
-1
7
9
20

【数据规模】

对于 $30\%$ 的数据，$1\le T,N\le 10$；
对于 $50\%$ 的数据，$1\le N\le 18$；
对于 $70\%$ 的数据，$1\le N\le 200$；
对于 $100\%$ 的数据，$1\le T\le 100,1\le \sum N\le 1000000$.