Description

矩形矩阵上除了星星就是小圆，他们势不两立，现在你需要消灭所有的星星，方法是用改正带。改正带每次只能覆盖两个相邻的格子（上下或者左右）。注意两个格子并不一定必须是星星，涂过改正带的格子也可以重复涂。为了节约改正带，你需要用最少的次数消灭所有的星星。

（不要问为什么，因为*代表指针，一看见就来气）

Format

Input

第一行输入测试样例数目$T$ ($0<T<10$).
第二行输入图的行数$R$ ($0<R<=40$), 列数$C$ ($0<C<=10$).
接下来R行输入图，其中*代表星星，$o$（小写）代表空白。

Output

输出消灭所有星星最少的次数。

Sample 1

Input

1
7 9
ooo**oooo
**oo*ooo*
o*oo**o**
ooooooooo
*******oo
o*o*oo*oo
*******oo

Output

17

Hint

暂无