B. Мадока и элегантный подарок
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Отец Мадоки достиг отметки в $$$1$$$ миллион подписчиков на Mathub! В честь этого вебсайт решил отправить ему персонализированную награду — Битовую Кнопку Mathub!

Награда представляет из себя таблицу из $$$n$$$ строк и $$$m$$$ столбцов, в каждой клетке которой записано число $$$0$$$ или $$$1$$$. Изучив таблицу, она вывела следующие характеристики:

  • Подпрямоугольник $$$A$$$ лежит в подпрямоугольнике $$$B$$$, если нет клетки, которая лежит внутри $$$A$$$, но при этом не лежит внутри $$$B$$$.
  • Два подпрямоугольника пересекаются, если найдется клетка, лежащая внутри обоих подпрямоугольников.
  • Подпрямоугольник называется чёрным, если в нём нет клетки со значением $$$0$$$.
  • Подпрямоугольник называется красивым, если он чёрный и не лежит в каком-то другом чёрном подпрямоугольнике.
  • Таблица называется элегантной, если никакие два красивых подпрямоугольника не пересекаются.

Например, на первой картинке красный подпрямоугольник является красивым, а на второй нет, так как он лежит внутри фиолетового подпрямоугольника.

Помогите Мадоке определить, является ли таблица элегантной.

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

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

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

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

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

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

Для каждого набора входных данных выведите «YES», если данная таблица является элегантной. Иначе, выведите «NO».

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

Пример
Входные данные
5
3 3
100
011
011
3 3
110
111
110
1 5
01111
4 5
11111
01010
01000
01000
3 2
11
00
11
Выходные данные
YES
NO
YES
NO
YES
Примечание

Во втором наборе входных данных таблица не элегантная, поскольку красный красивый подпрямоугольник пересекается с фиолетовым.

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