题目描述

点此下载 2024 年实验室二面题解

在我的世界中甘蔗有个奇怪的设定，那就是必须生长在水边的陆地上。在一个$n*m$的网格中，点$(x,y)$可以种甘蔗当且仅当其是陆地且其上下左右与其相邻的点至少有一个是水源，每个点最多只能种1个甘蔗。现在给你一个仅由'$.$'和'$*$'构成的矩形网格，'$.$'表示陆地，'$*$'表示水源，请你回答该网格最多可以种多少甘蔗。

输入描述

第一行输入一个整数T代表测试用例个数。

接下来一行输入两个整数$n,m$(分别表示网格的行数和列数)。

接下来n行，每行输入长度为$m$且仅包含'$.$'和'$*$'的字符串代表网格的每一行。

$1<=T,n,m<=100$

输出描述

输出T行，每行表示每个测试用例最多能种多少甘蔗。

示例 1

输入

1
4 5
....*
..*..
..***
*****

输出

7