**Замечание: Время на тест в этой задаче 4 сек, в 2 раза больше, чем по умолчанию.**
Беси использует свой изящный телескоп чтобы сделать фотографии всех звёзд
на ночном небе. Её телескоп может сделать фото \(N \times N\) (\(1 \leq N \leq 1000\))
пикселов, где каждый пиксел это или звезда, или пустое небо. Каждая звезда будет
представлена ровно одним пикселом, и никакие две звезды на разделяют один и тот же пиксел.
Ночью происходит что-то странное со звёздами на небе. Каждая звезда или исчезает
или перемещается на \(A\) пикселов вправо и на \(B\) пикселов вниз (\(0 \leq A,B \leq N\)).
Если звезда исчезает или перемещается за границу фото, она больше не появляется на
втором фото.
Беси делает фотографии до и после перемещений, но после экспериментов, она
случайно наложила одну фотографию на другую. Теперь она видит белые пикселы,
которые были пустыми на обеих фотографиях, серые пикселы, где звезда была ровно
на одном фото и чёрные пикселы, где была звезда на обоих фотографиях. Беси
также помнит, что на второй фотографии не появились новые звёзды, поэтому
первая фотография содержит все звёзды ночного неба. Если не существует исходного
положения звёзд, которое может произвести финальное фото, выведите \(-1\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(T\), далее следуют
\(T\) подтестов.
Первая строка каждого подтеста содержит \(N\) \(A\) \(B\).
Далее следуют \(N\) строк, каждая из которых представляет одну строку наложенных
фотографий. \(i\)-ая строка представлена строкой \(c_{i,1}c_{i,2}\dots c_{i,N}\),
где каждый \(c_{i,j} \in \{W,G,B\}\), представляющих белый, серый и чёрный цвет
соответственно.
Гарантируется, что сумма \(N^2\) для всех подтестов не превысит \(10^7\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите минимальное количество звёзд, которые существовали
до сдвига или \(-1\) если это невозможно определить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
3 0 0
WWB
BBB
GGG
|
7
|