SP15328 HXH - Hunter x Hunter

Gon 和 Killua 是两位非常有才华的猎人，他们在战斗中技艺高超。众所周知，Killua 的速度和机智超过 Gon，而 Gon 的力量和决心则更胜一筹。这使得他们的组合几乎无懈可击（只需再磨练一段时间，他们就能成为史上最杰出的猎人）。作为一支出色的团队，他们决定联手击败尽可能多的敌人。经过一番策划，敌人们被安排在一个 $N \times N$ 的网格中。Gon 从 $(0, 0)$ 开始，Killua 从 $(n-1, n-1)$ 出发。为了最大化击败的敌人数量，Gon 只能向右或向下移动，而 Killua 只能向左或向上移动。他们会计算击败的敌人数，当两人相遇在同一格时，彼此击掌庆祝。如果未能击掌，他们会非常失望，所以必须确保击掌这一行动的完成。 然而，Killua 想要这次行动格外完美，因此希望制定一个新的计划。但他不确定最佳路径。作为一个出色的程序员，你需要帮助他找出能够使他们在相遇时共同击败最多敌人的方法。只有得到了这个信息，Killua 才能完善他的计划。 请注意，他们的移动是同步的，如果任何一个人无法继续前进，则这一步无效，并且两人不能停留在原地。 网格中的元素含义如下： - `#` 表示障碍物，Gon 和 Killua 无法穿越。 - `.` 表示可行走的区域。 - `*` 表示敌人。

输入包含多个测试用例。每个测试用例以一个整数 $T$ 开头，表示测试用例的数量。接下来，每个测试用例开始于一个整数 $2 \leq N \leq 500$，表示网格大小，随后是该网格的描述。

对于每个测试用例，输出两人能够共同击败的最大敌人数，并在最终击掌庆祝。如果无法实现，请输出 -1。

- $2 \leq N \leq 500$ ### 示例 **输入** ``` 1 5 ..\*.. .\*..\* \#...\* ..\*.. ..... ``` **输出** ``` 3 ``` **说明** 如果没有击掌这一限制，他们可以击败所有 5 个敌人，但因为需要同时不间断地移动并相遇击掌，他们只能在击杀 3 个敌人后相聚。Killua 击败 2 个敌人，Gon 击败 1 个敌人。 **本翻译由 AI 自动生成**