문제

Note: The time limit for this problem is 4s, twice the default.

Bessie is using her nifty telescope to take photos of all the stars in the night sky. Her telescope can capture an $N \times N$ ($1 \leq N \leq 1000$) photo of the stars where each pixel is either a star or empty sky. Each star will be represented by exactly one pixel, and no two distinct stars share the same pixel.

Overnight, something strange happens to the stars in the sky. Every star either disappears or moves $A$ pixels to the right, and $B$ pixels downwards ($0 \leq A,B \leq N$). If a star disappears or moves beyond the photo boundary, it no longer appears in the second photo.

Bessie took photos before and after the shifting positions, but after experimenting in Mootoshop, she accidentally superimposed one photo onto the other. Now, she can see white pixels where both photos were empty, gray pixels where stars existed in exactly one photo, and black pixels where there was a star in both photos. Bessie also remembers that no new stars moved into the frame of the second photo, so her first photo contains all of the stars in the night sky.

Given the final photo, determine the minimum possible number of stars in the sky before the shifting incident for $T$ ($1 \leq T \leq 1000$) independent test cases. If no arrangement of stars can produce the given final photo, output $-1$.

입력

The first line of input contains $T$ and $T$ test cases will follow.

The first line of each test case will contain $N$ $A$ $B$.

Then follow $N$ lines each representing one row of the superimposed photo. The $i$th row from the top is represented by a string $c_{i,1}c_{i,2}\dots c_{i,N}$, where each $c_{i,j} \in \{W,G,B\}$, representing the colors white, gray, and black respectively.

It is guaranteed that the sum of $N^2$ over all test cases will not exceed $10^7$.

출력

For each test case, output the minimum number of stars that existed before the shifting, or $-1$ if impossible.

예제 입력 1

1
3 0 0
WWB
BBB
GGG

예제 출력 1

7

예제 입력 2

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

예제 출력 2

4
-1
4

점수

Input 3: $A=B=0$Inputs 4-7: $A=1, B=0, N\le 10$Inputs 8-9: $A=1, B=0$Inputs 10-12: No additional constraints.