Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem H: 三队-杭州-战舰

Problem H: 三队-杭州-战舰

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 47  Solved: 16
[Submit][Status][Web Board]

Description

给你一张 n*m的矩阵图形,’*’表示空地,’o’表示浮冰,’#’表示冰山 ,你可以在空地上放战舰,但是同一行或同一列只能放一个战舰。若两个战舰想放在同一行或同一列上,那么它们之间必须要有冰山相隔。然后问你在这张图上最多可以放多少个战舰?

Input

第一行包含一个整数T,代表测试组数。

每组测试数据的第一行两个整数n,m。

接下来n行,每行m个字符。字符只可能是’*’,’o’,’#’三者之一。

限制:1<T<12,1<=n,m<=50。

Output

对于每组数据,输出一行,一个整数,代表最多可安置的战舰数量。

Sample Input

2
4 4
*ooo
o###
**#*
ooo*
4 4
#***
*#**
**#*
ooo#

Sample Output

3
5

HINT

[Submit][Status][Web Board]