建围墙

题目描述

在某个方格棋盘上有一些塔楼棋子：

现在 Karl 想在棋盘上建一道正方形的护城墙，使得墙能够框住更多的塔楼，例如：

请你计算能同时被护城墙框住的塔楼最大数量。

现在你要解决 $t$ 个这样的问题，每次告诉你 $n$ 行 $m$ 列棋盘的情况，请你计算出结果。

输入格式

第一行一个整数 $t$。

接下来 $t$ 个块：

第一行两个正整数 $n,m$，表示棋盘的大小。

接下来 $n$ 行每行 $m$ 个字符，表示棋盘的情况：

• X：该格子有塔楼。
• O：该格子是空的。

输出格式

$t$ 行，每行一个整数表示答案。

样例 #1

样例输入 #1

1
2 2
X O
O X

样例输出 #1

2

样例 #2

样例输入 #2

2
2 3
O X X
X O X
3 3
X X X
X X X
X X X

样例输出 #2

3
8

提示

【数据范围】

对于所有数据，$1 \leq t \leq 10^2$，$2 \leq n,m \leq 10^2$。

测试点编号	$t$	$n,m$	特殊约束
$1 \sim 6$	$\leq 10$	$\leq 10$	无
$7 \sim 12$	$\leq 10$	$\leq 10^2$	无
$13 \sim 20$	$\leq 10^2$	$\leq 10^2$	无

【样例 1 解释】

第一组数据中，最多能框住 $2$ 个塔楼：

【样例 2 解释】

第一组数据中，最多能框住 $3$ 个塔楼：

第二组数据中，最多能框住 $8$ 个塔楼：