Minimum Initial Stars

Bessie is photographing the night sky with her telescope. Her telescope can capture an N × N (\(1 \le N \le 1000\)) image where each pixel is either a star or empty sky. In the first photograph, each star occupies exactly one pixel and no two stars overlap.

Then, a strange event occurs: each star either disappears or moves exactly \(A\) pixels to the right and \(B\) pixels down, where \(0 \le A, B \le N\). If a star disappears or if its move causes it to go outside the image, it no longer appears in the second photograph. Bessie took both photos. However, due to an accident in her lab, the two photos were overlaid. In the final overlaid image:

• A white pixel means both photos had sky.
• A gray pixel means exactly one of the two photos had a star.
• A black pixel means both photos contained a star in that pixel.

Moreover, Bessie remembers that no new stars moved into the range of the second photograph — the first photograph contained every star in the sky. Given the final merged image for \(T\) (\(1 \le T \le 1000\)) test cases, determine the minimum possible number of stars that could have been present in the sky before the event. If no arrangement of stars in the first photograph could have produced the given final image, output \(-1\).

Note: The time limit for this problem is 4 seconds (typically, twice the usual limit).

All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with an integer \(T\), the number of test cases. For each test case, the first line contains three integers \(N\), \(A\), and \(B\). Then follow \(N\) lines, each containing a string of length \(N\). Each character is one of:

• W representing a white pixel,
• G representing a gray pixel,
• B representing a black pixel.

You may assume that the final image is always an \(N \times N\) grid.

outputFormat

For each test case, output a single integer: the minimum possible number of stars in the first photograph, or \(-1\) if no valid arrangement exists.

sample

1
2 1 1
GG
GG

3