B. Соединяй
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано исходное поле размером $$$n \times n$$$, в котором некоторые клетки окрашены в чёрный цвет, а остальные — в белый. При желании вы можете закрашивать любые белые клетки в чёрный цвет.

В конце необходимо выполнить все перечисленные условия:

  1. В поле должна быть хотя бы одна чёрная клетка.
  2. Все чёрные клетки должны быть ортогонально связаны, то есть из любой чёрной клетки можно добраться до любой другой чёрной, переходя только по общим сторонам клеток и посещая только чёрные клетки. Переход «по диагонали через угол» запрещён.
  3. Не должно быть трёх подряд идущих чёрных клеток, расположенных вертикально или горизонтально.

Закрашивать чёрные клетки в белый цвет нельзя.

Необходимо определить, можно ли закрасить некоторые белые клетки в чёрный так, чтобы все эти условия выполнялись.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \leq n \leq 100$$$) — размер поля.

Следующие $$$n$$$ строк содержат по $$$n$$$ символов — описание поля, где каждый символ представляет одну клетку:

  • . — белая клетка;
  • # — чёрная клетка.

Гарантируется, что сумма значений $$$n$$$ по всем наборам данных не превышает $$$2000$$$.

Выходные данные

Для каждого набора данных выведите «YES», если можно закрасить некоторые белые клетки в чёрный цвет так, чтобы все условия выполнялись, и «NO» в противном случае.

Буквы можно выводить в любом регистре. Например, строки «yEs», «yes», «Yes» и «YES» будут восприняты как положительный ответ.

Пример
Входные данные
11
1
.
1
#
3
.##
.##
...
3
#..
.#.
..#
3
###
...
...
3
#.#
...
.#.
4
####
#..#
#..#
####
3
..#
...
.#.
3
..#
#..
...
5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
5
...#.
...#.
.....
##...
.....
Выходные данные
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
Примечание

В первом наборе данных нет чёрных клеток, поэтому нужно закрасить одну клетку в чёрный цвет.

Во втором и третьем наборах данных поле изначально удовлетворяет всем условиям.

В четвёртом наборе данных одним из возможных решений является:

##.
.##
..#

В пятом наборе данных поле изначально нарушает условие «Не должно быть трёх подряд идущих чёрных клеток, расположенных вертикально или горизонтально», поэтому решения нет.

В шестом наборе данных можно показать, что невозможно соединить клетки, не нарушив условие о трёх подряд чёрных клетках.