eolymp
bolt
Try our new interface for solving problems
Problems

Триомино

Триомино

Time limit 1 second
Memory limit 64 MiB

Фигуркой триомино называют связную фигуру, состоящую из трех квадратов. Существует всего два различных типа таких фигурок — они изображены на рисунке. Все другие отличаются только поворотами. Прямоугольное поле размером M строк и N столбцов считается заполненным фигурками триомино, если:

  1. Каждая фигурка находится в пределах поля и накрывает ровно три клетки.

  2. Фигурки не накладываются.

  3. Пустых (не покрытых фигуркой) клеток не более двух.

Заполненное фигурками поле можно представить в виде прямоугольной таблицы. Значение 0 обозначает незаполненную клетку. Одинаковые натуральные значения обозначают, что клетки принадлежат одной фигурке, разные — разным.

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

Input data

Первая строка входного файла содержит единственное целое число T (2T10) — количество прямоугольных таблиц. Далее идет T блоков такой структуры. Первая строка блока содержит два целых числа M и N (1M200, 1 N 200) — количество строк и количество столбцов соответствующей таблицы. Далее идет M строк по N целых чисел в каждой. Значения этих чисел от 0 до [M×N/3] включительно. Размер входного файла не будет перевышать 512 Kb.

Output data

Выходной файл должен содержать T строк, в каждой — слово YES или слово NO (большими латинскими буквами) обозначающее, задает ли соответствующая таблица правильно заполненное фигурками триомино поле.

Прмечание: Рисунок к первому блоку:

Examples

Input example #1
2
4 8
1 2 2 2 6 7 7 9
1 4 4 3 6 7 8 9
1 0 4 3 6 8 8 9
10 10 10 3 0 5 5 5
2 6
1 1 2 2 1 1
0 1 0 2 0 1
Output example #1
YES
NO
Author Илья Порублёв
Source 2012 XXV All-Ukrainian Informatics Olympiad, Vinnitsa, March 24 - 28, Round 1