E. Полигон
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Полигон — это не только лучшая платформа для разработки задач, но и квадратная матрица со стороной $$$n$$$, изначально состоящая из нулей.

На полигоне проводятся боевые учения. Поэтому над каждой клеткой в первой строке и слева от каждой клетки первого столбца находится пушка. Таким образом, всего есть $$$2n$$$ пушек.

Изначальный полигон для $$$n=4$$$.

Пушки стреляют единицами. В один момент времени стреляет не больше одной пушки. Когда единица вылетает из пушки, то она летит вперед, по направлению выстрела, до тех пор, пока не столкнется с границей полигона или другой единицей. После этого она занимает клетку, в которой находилась перед столкновением, и остается там. Изучите примеры для лучшего понимания.

Более формально:

  • если пушка, стоящая в строке $$$i$$$ перед первым столбцом, стреляет единицей, то единица начинает свой полет из клетки ($$$i, 1$$$) и заканчивает в какой-то клетке ($$$i, j$$$);
  • если пушка, стоящая в столбце $$$j$$$ над первой строкой, стреляет единицей, то единица начинает свой полет из клетки ($$$1, j$$$) и заканчивает в какой-то клетке ($$$i, j$$$).

Например, рассмотрим следующую последовательность выстрелов:

1. Стреляет пушка в строке $$$2$$$.                         2. Стреляет пушка в строке $$$2$$$.                         3. Стреляет пушка в столбце $$$3$$$.

У вас на столе лежит отчет с проведенных учений. Этот отчет является квадратной матрицей с длиной стороны $$$n$$$, состоящей из нулей и единиц. Вам интересно, действительно ли произошли учения. Другими словами, существует ли такая последовательность выстрелов, что в конце получится заданная матрица?

Каждая пушка может сделать произвольное количество выстрелов. Перед началом учений полигон состоит из нулей.

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

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

Каждый набор начинается со строки, в которой записано целое число $$$n$$$ ($$$1 \le n \le 50$$$) — размер полигона.

Далее следуют $$$n$$$ строк длины $$$n$$$, состоящих из нулей и единиц — матрица полигона после проведения учений.

Суммарная площадь матриц во всех наборах тестовых данных в одном тесте не превосходит $$$10^5$$$.

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

Для каждого набора тестовых данных выведите:

  • YES, если существует последовательность выстрелов, приводящая к заданной матрице;
  • NO, если такой последовательности не существует.

Буквы в словах YES и NO можно выводить в любом регистре.

Пример
Входные данные
5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111
Выходные данные
YES
NO
YES
YES
NO
Примечание

Первый набор тестовых данных примера разобран в условии.

Ответ на второй набор NO, так как, вылетев из любой пушки, единица в клетке ($$$1, 1$$$) продолжила бы свой полет дальше.