题目描述

注意：本题的时间限制为 4 秒，通常限制的 2 倍。

Bessie 正在使用她超酷的望远镜拍摄夜空中所有星星的照片。她的望远镜能够拍摄到一张 $N \times N$（$1 \leq N \leq 1000$）的星星照片，其中每个像素是一颗星星或者空旷的天空。每颗星星可由恰好一个像素表示，并且没有两颗不同的星星位于同一像素内。

一夜之间，一些奇怪的事情发生在了天空中的星星之上。每颗星星要么消失，要么向右移动 $A$ 像素，并且向下移动 $B$ 像素（$0 \leq A,B \leq N$）。如果一颗星星消失或移动超出照片边界，它将不再出现在第二张照片中。

Bessie 在星星移动位置之前和之后拍了照片，但在 Mootoshop 中进行了一些实验后，她不小心将一张照片叠加到了另一张上。现在，她可以在两张照片都是天空的位置看到白色（white）像素，在星星仅存在于恰好一张照片的位置看到灰色（gray）像素，而在两张照片中都有星星的位置看到黑色（black）像素。Bessie 同时记得没有新的星星移动入第二张照片的范围，从而她的第一张照片包含了夜空中所有的星星。

对于 $T$（$1 \leq T \leq 1000$）个独立的测试用例，给定最终的照片，求在移动事件发生之前天空中星星的最小可能数量。如果不存在星星的排列可以产生给定的最终照片，输出 $-1$。

输入格式

输入的第一行包含 $T$，以下为 $T$ 个测试用例。

每个测试用例的第一行包含 $N$，$A$，$B$。

以下 $N$ 行，每行表示叠加后的照片的一行。从上到下第 $i$ 行由一个字符串 $c_{i,1}c_{i,2}\dots c_{i,N}$ 表示，其中 $c_{i,j} \in \{\texttt{W,G,B}\}$，分别表示颜色为白色，灰色以及黑色。

输入保证所有测试用例的 $N^2$ 之和不超过 $10^7$。

输出格式

对于每一个测试用例，输出移动之前存在的星星的最小数量，或 $-1$ 表示不可能。

1
3 0 0
WWB
BBB
GGG

7

3
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWW

4
-1
4

提示

样例解释

在样例 #1 中，没有移动发生。第一张照片如下（. 表示天空，* 表示星星）：

..*
***
***

第二张照片中最下方一行的星星都消失了，如下：

..*
***
...

这是产生叠加后照片的唯一方式，所以初始时星星的最小可能数量为 $7$。

对于样例 #2，在第一个测试用例中，初始时至少有 $4$ 颗星星。如果我们令 $(r,c)$ 表示从上到下第 $r$ 行和从左到右第 $c$ 列的交点，一种可能性是它们最初位于 $(1,1)$，$(3,2)$，$(2,2)$ 和 $(1,3)$。除了位于 $(2,2)$ 的星星消失之外，其他所有星星都移动了。

在第二个测试用例中，在给定的移动方式下，没有任何初始照片中的星星排列可以产生中间的黑色像素。

在第三个测试用例中，初始时至少有 $4$ 颗星星。一种可能性是它们最初位于 $(1,1)$，$(1,2)$，$(1,3)$ 和 $(2,1)$。在第二张照片中，原先位于 $(1,1)$ 的星星消失了，原先位于 $(1,3)$ 的星星移出了照片边界。其他两颗星星向右移动了 $1$ 像素。

子任务

• 测试点 3：$A=B=0$。
• 测试点 4-7：$A=1$，$B=0$，$N\le 10$。
• 测试点 8-9：$A=1$，$B=0$。
• 测试点 10-12：没有额外限制。