Madoka's father just reached $1$ million subscribers on Mathub! So the website decided to send him a personalized award — The Mathhub's Bit Button!

The Bit Button is a rectangular table with $n$ rows and $m$ columns with $0$ or $1$ in each cell. After exploring the table Madoka found out that:

A subrectangle $A$ is contained in a subrectangle $B$ if there's no cell contained in $A$ but not contained in $B$.

Two subrectangles intersect if there is a cell contained in both of them.

A subrectangle is called black if there's no cell with value $0$ inside it.

A subrectangle is called nice if it's black and it's not contained in another black subrectangle.

The table is called elegant if there are no two nice intersecting subrectangles.

For example, in the first illustration the red subrectangle is nice, but in the second one it's not, because it's contained in the purple subrectangle.

Help Madoka to determine whether the table is elegant.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 200$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two positive integers $n, m$ ($1 \le n, m \le 100$).

The next $n$ lines contain strings of length $m$ consisting of zeros and ones — the description of the table.

It is guaranteed that the sum of the values of $n$ and the sum of the values of $m$ for all test cases do not exceed $777$.


-----Output-----

For each test case print "YES" if its table is elegant or print "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).


-----Examples-----

Input
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
Output
YES
NO
YES
NO
YES


-----Note-----

In the second test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.

In the fourth test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Graph algorithms

Implementation

Constructive algorithms


Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for row in range(n)]

	def ind(i, j):
		return (i - 1) * m + j

	def cnt(i, j):
		return [a[i][j], a[i][j + 1], a[i + 1][j], a[i + 1][j + 1]].count('1')
	flag = False
	for i in range(n - 1):
		if flag:
			break
		for j in range(m - 1):
			if cnt(i, j) == 3:
				flag = True
				break
	print('NO' if flag else 'YES')


import sys
from math import *
inf = 10 ** 9
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())

	def m1(i, j):
		if j < m - 1 and a[i][j + 1] == '1' and (i < n - 1) and (a[i + 1][j] == '1') and (a[i + 1][j + 1] != '1') or (j < m - 1 and a[i][j + 1] == '1' and (i > 0) and (a[i - 1][j] == '1') and (a[i - 1][j + 1] != '1')) or (j > 0 and a[i][j - 1] == '1' and (i < n - 1) and (a[i + 1][j] == '1') and (a[i + 1][j - 1] != '1')) or (j > 0 and a[i][j - 1] == '1' and (i > 0) and (a[i - 1][j] == '1') and (a[i - 1][j - 1] != '1')):
			return True
		return False
	f = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == '1' and m1(i, j):
				f = 1
				print('NO')
				break
		if f:
			break
	else:
		print('YES')


def check(s1, s2):
	f = True
	cnt = 0
	h = True
	for i in range(len(s1)):
		if s1[i] == s2[i] or h:
			h = True
			f = False
			cnt += 1
			if s1[i] == s2[i] and s1[i] == '1':
				h = False
				if i - 1 >= 0:
					if s1[i - 1] != s2[i - 1]:
						cnt = -100
	if cnt == len(s1):
		f = True
	return f

def rotate(s):
	return [[s[j][i] for j in range(len(s))] for i in range(len(s[0]) - 1, -1, -1)]
import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
	for _ in range(int(input())):
		f = True
		(x, y) = map(int, input().split())
		s = [list(str(input())[:-1]) for _ in range(x)]
		ss = rotate(s)
		for i in range(x - 1):
			f = check(s[i], s[i + 1])
			if not f:
				break
		for i in range(y - 1):
			if not f:
				break
			f = check(ss[i], ss[i + 1])
		if f:
			print(f'YES\n')
		else:
			print(f'NO\n')
main()


case = int(input())
for i in range(case):
	tables = input().split(' ')
	n = int(tables[0])
	m = int(tables[1])
	lines = []
	for j in range(n):
		line = input()
		lines.append(line)
	if n == 1 or m == 1:
		print('YES')
		continue
	for j in range(n - 1):
		line1 = lines[j]
		line2 = lines[j + 1]
		printed_flag = False
		state = 0
		for k in range(m):
			temp_state = 0
			same_is = line1[k] == line2[k]
			if not same_is:
				temp_state = 2
			elif line1[k] == '1':
				temp_state = 1
			if temp_state + state == 3:
				print('NO')
				printed_flag = True
				break
			state = temp_state
		if printed_flag:
			break
	if not printed_flag:
		print('YES')


def solve():
	(N, M) = map(int, input().split())
	arr = []
	for i in range(N):
		a1 = input()
		arr.append(a1)
	i = 0
	while i < N - 1:
		j = 0
		while j < M - 1:
			a1 = arr[i][j]
			a2 = arr[i][j + 1]
			a3 = arr[i + 1][j]
			a4 = arr[i + 1][j + 1]
			if a1 == '1' and a2 == '0' and (a3 == '1') and (a4 == '1'):
				return 'NO'
			elif a1 == '0' and a2 == '1' and (a3 == '1') and (a4 == '1'):
				return 'NO'
			elif a1 == '1' and a2 == '1' and (a3 == '1') and (a4 == '0'):
				return 'NO'
			elif a1 == '1' and a2 == '1' and (a3 == '0') and (a4 == '1'):
				return 'NO'
			j += 1
		i += 1
	return 'YES'
remained_test_Cases = 1
remained_test_Cases = int(input())
while remained_test_Cases > 0:
	print(solve())
	remained_test_Cases -= 1


for _ in range(int(input())):
	matrix = []
	(m, n) = map(int, input().split())
	for iii in range(m):
		matrix.append(input())
	if n == 1 or m == 1:
		print('YES')
	else:
		res = True
		k = ''
		for i in range(m - 1):
			for j in range(n - 1):
				k += matrix[i][j:j + 2] + matrix[i + 1][j:j + 2]
				if k.count('0') == 1 and k.count('1') == 3:
					res = False
					break
				k = ''
			else:
				continue
			break
		if res == False:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for z in range(n):
		s = input().rstrip()
		a.append(s)
	f = 0
	for i in range(0, n):
		for j in range(0, m):
			if a[i][j] == '1':
				if j >= 1:
					if a[i][j - 1] == '1':
						if i < n - 1:
							if a[i + 1][j - 1] != a[i + 1][j]:
								f = 1
								break
					elif i < n - 1:
						if a[i + 1][j - 1] == '1' and a[i + 1][j] == '1':
							f = 1
							break
			elif j >= 1:
				if a[i][j - 1] == '1':
					if i < n - 1:
						if a[i + 1][j - 1] == '1' and a[i + 1][j] == '1':
							f = 1
							break
		if f == 1:
			break
	if f == 1:
		print('NO')
	else:
		for j in range(1, m):
			if a[n - 1][j] == '1':
				if a[n - 1][j - 1] == '1':
					if a[n - 2][j - 1] != a[n - 2][j]:
						f = 1
						break
		if f == 1:
			print('NO')
		else:
			print('YES')


def sum(x, y):
	ans = ''
	for i in range(len(x)):
		ans += str(int(x[i]) + int(y[i]))
	return ans

def func(x):
	if len(x) == 1:
		return False
	cur = x[0]
	for i in range(1, len(x)):
		if x[i] != cur:
			if x[i] == '1' and cur == '2' or (x[i] == '2' and cur == '1'):
				return True
			cur = x[i]
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for _ in range(n):
		l.append(input())
	for i in range(n - 1):
		ans = sum(l[i], l[i + 1])
		if func(ans):
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for _ in range(0, t):
	(n, m) = map(int, input().split())
	a = []
	for j in range(0, n):
		s = input()
		a.append(s)
	flag = 0
	for i in range(0, n):
		for j in range(0, m):
			if a[i][j] == '1':
				if i + 1 < n and a[i + 1][j] == '1' and (j + 1 < m) and (a[i][j + 1] == '1') and (a[i + 1][j + 1] == '0'):
					flag = 1
				if i + 1 < n and a[i + 1][j] == '1' and (j - 1 >= 0) and (a[i][j - 1] == '1') and (a[i + 1][j - 1] == '0'):
					flag = 1
				if i - 1 >= 0 and a[i - 1][j] == '1' and (j + 1 < m) and (a[i][j + 1] == '1') and (a[i - 1][j + 1] == '0'):
					flag = 1
				if i - 1 >= 0 and a[i - 1][j] == '1' and (j - 1 >= 0) and (a[i][j - 1] == '1') and (a[i - 1][j - 1] == '0'):
					flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	g = []
	czy = True
	for i in range(n):
		g.append(input())
	for i in range(n):
		if not czy:
			break
		for j in range(m):
			if g[i][j] == '1':
				if i != 0 and j != 0:
					if g[i - 1][j] == '1' and g[i][j - 1] == '1' and (g[i - 1][j - 1] == '0'):
						czy = False
						break
				if i != 0 and j != m - 1:
					if g[i - 1][j] == '1' and g[i][j + 1] == '1' and (g[i - 1][j + 1] == '0'):
						czy = False
						break
				if i != n - 1 and j != 0:
					if g[i + 1][j] == '1' and g[i][j - 1] == '1' and (g[i + 1][j - 1] == '0'):
						czy = False
						break
				if i != n - 1 and j != m - 1:
					if g[i + 1][j] == '1' and g[i][j + 1] == '1' and (g[i + 1][j + 1] == '0'):
						czy = False
						break
	if czy:
		print('YES')
	else:
		print('NO')


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	for k in range(n):
		Q = []
		for j in input():
			Q.append(int(j))
		d.append(Q)
	br = 0
	if n == 1:
		print('YES')
	else:
		for k in range(n - 1):
			for j in range(m - 1):
				z = d[k + 1][j] + d[k][j] + d[k + 1][j + 1] + d[k][j + 1]
				if z == 3:
					print('NO')
					br = 1
				if br == 1:
					break
			if br == 1:
				break
		if br == 0:
			print('YES')


def solve():
	for i in range(n - 1):
		for j in range(m - 1):
			if a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1] == 3:
				return 'NO'
	return 'YES'
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	a = []
	for _ in range(n):
		a.append(list(map(int, input())))
	print(solve())


number_tests = int(input())

def checkResult(list_table, n_rows, m_cols):
	if n_rows > 1 and m_cols > 1:
		for row in range(n_rows - 1):
			for col in range(m_cols - 1):
				count = 0
				if list_table[row][col] == '1':
					count += 1
				if list_table[row + 1][col] == '1':
					count += 1
				if list_table[row][col + 1] == '1':
					count += 1
				if list_table[row + 1][col + 1] == '1':
					count += 1
				if count == 3:
					return 'NO'
	return 'YES'
for test in range(number_tests):
	rowcol = input().split()
	n_rows = int(rowcol[0])
	m_cols = int(rowcol[1])
	list_table = []
	for row in range(n_rows):
		list_table.append(input())
	print(checkResult(list_table, n_rows, m_cols))


def main():
	t = int(input())
	while t:
		t -= 1
		(n, m) = list(map(int, input().split()))
		arr = [[0 for _ in range(m)] for _ in range(n)]
		for i in range(n):
			s = input()
			for (j, c) in enumerate(s):
				arr[i][j] = int(c)
		if check(arr, n, m):
			print('YES')
		else:
			print('NO')

def check(arr, n, m):
	for i in range(n - 1):
		for j in range(m - 1):
			sum = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]
			if sum == 3:
				return False
	return True
main()


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		s = input()
		arr.append(s)
	found = False
	for i in range(n - 1):
		for j in range(m - 1):
			if [arr[i][j], arr[i][j + 1], arr[i + 1][j + 1], arr[i + 1][j]].count('0') == 1:
				found = True
				break
		if found:
			print('NO')
			break
	else:
		print('YES')


for g in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	for i in range(n):
		l += [input()]
	f = 1
	for x in range(n - 1):
		for y in range(m - 1):
			if [l[x][y], l[x + 1][y + 1], l[x][y + 1], l[x + 1][y]].count('0') == 1:
				f = 0
				break
	if f:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = [input() for j in range(n)]
	flag = 0
	for j in range(n):
		for k in range(m):
			if l[j][k] == '1':
				if j - 1 >= 0 and k - 1 >= 0 and (l[j - 1][k] == '1') and (l[j][k - 1] == '1') and (l[j - 1][k - 1] == '0'):
					print('NO')
					flag = -1
					break
				if j - 1 >= 0 and k + 1 <= m - 1 and (l[j - 1][k] == '1') and (l[j][k + 1] == '1') and (l[j - 1][k + 1] == '0'):
					print('NO')
					flag = -1
					break
				if j + 1 <= n - 1 and k + 1 <= m - 1 and (l[j + 1][k] == '1') and (l[j][k + 1] == '1') and (l[j + 1][k + 1] == '0'):
					print('NO')
					flag = -1
					break
				if j + 1 <= n - 1 and k - 1 >= 0 and (l[j + 1][k] == '1') and (l[j][k - 1] == '1') and (l[j + 1][k - 1] == '0'):
					print('NO')
					flag = -1
					break
		if flag == -1:
			break
	if flag == 0:
		print('YES')


t = int(input())
for g in range(t):
	a = []
	b = []
	f = 0
	(n, m) = map(int, input().split())
	for j in range(n):
		a.append(input())
	for i in range(n - 1):
		for j in range(m - 1):
			if a[i][j] == '1':
				if a[i][j + 1] == '1' and a[i + 1][j] == '1':
					if a[i + 1][j + 1] != '1':
						f = 1
						break
				if a[i][j + 1] == '1' and a[i + 1][j] != '1':
					if a[i + 1][j + 1] == '1':
						f = 1
						break
				if a[i][j + 1] != '1' and a[i + 1][j] == '1':
					if a[i + 1][j + 1] == '1':
						f = 1
						break
			if a[i][j] == '0':
				if a[i][j + 1] == '1' and a[i + 1][j] == '1':
					if a[i + 1][j + 1] == '1':
						f = 1
						break
		if f == 1:
			break
	if f == 0:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input())))
	su = 0
	ans = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			su = l[i][j] + l[i + 1][j] + l[i][j + 1] + l[i + 1][j + 1]
			if su == 3:
				ans = 'NO'
				break
		if ans == 'NO':
			break
	print(ans)


from re import L
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def func():
	(n, m) = mul()
	gp = []
	for i in range(n):
		gp.append([int(i) for i in strng()])
	for i in range(n - 1):
		for j in range(m - 1):
			if gp[i][j] + gp[i + 1][j] + gp[i][j + 1] + gp[i + 1][j + 1] == 3:
				return 'NO'
	return 'YES'
t = inp()
for i in range(t):
	print(func())


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	for i in range(n):
		d.append(list(map(int, input())))
	res = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			if d[i][j] + d[i + 1][j] + d[i][j + 1] + d[i + 1][j + 1] == 3:
				res = 'NO'
				break
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input())))
	ans = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			if a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1] == 3:
				ans = 'NO'
				break
	print(ans)


t = int(input())

def verify_no_bad_edge(arr, n, m):
	i = 0
	j = 0
	seen = set()
	while i < n:
		if (i, j) not in seen:
			seen.add((i, j))
			if arr[i][j] == '1':
				x = i
				y = j
				while x < n and y < m and (arr[x][y] == '1'):
					seen.add((x, y))
					y += 1
				mx_col = y
				x += 1
				y = j
				while x < n:
					if arr[x][y] == '1':
						if y != 0 and arr[x][y - 1] != '0':
							return False
						while y < mx_col and arr[x][y] == '1':
							seen.add((x, y))
							y += 1
						if y < mx_col or (mx_col < m and arr[x][y] == '1'):
							return False
						x += 1
						y = j
					else:
						while y < mx_col and arr[x][y] == '0':
							seen.add((x, y))
							y += 1
						if y < mx_col:
							return False
						break
		j += 1
		if j >= m:
			j = 0
			i += 1
	return True
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		arr.append(input())
	if verify_no_bad_edge(arr, n, m):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	g = []
	for i in range(n):
		g.append(input())
	if n == 1 or m == 1:
		print('YES')
	else:
		f = False
		for i in range(n - 1):
			for j in range(m - 1):
				c = 0
				if g[i][j] == '1':
					c += 1
				if g[i + 1][j] == '1':
					c += 1
				if g[i][j + 1] == '1':
					c += 1
				if g[i + 1][j + 1] == '1':
					c += 1
				if c == 3:
					f = True
					break
			if f:
				break
		if f:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(int, list(str(input())))))
	flag = 0
	for i in range(1, n):
		for j in range(1, m):
			if arr[i - 1][j - 1] + arr[i][j] == 2 and arr[i - 1][j] + arr[i][j - 1] == 1 or (arr[i - 1][j - 1] + arr[i][j] == 1 and arr[i - 1][j] + arr[i][j - 1] == 2):
				flag = 1
				print('NO')
				break
		if flag == 1:
			break
	else:
		print('YES')


t = int(input())
for u in range(t):
	(n, m) = list(map(int, input().split()))
	arr = []
	tot = 0
	for i in range(n):
		arr.append([int(l) for l in input()])
	for i in arr:
		for k in i:
			tot += k
	if n == 1 or m == 1:
		print('YES')
		continue
	start = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]
	if start == 3:
		print('NO')
		continue
	ans = 'YES'
	for i in range(0, n - 1):
		for k in range(0, m - 1):
			if arr[i][k] + arr[i][k + 1] + arr[i + 1][k] + arr[i + 1][k + 1] == 3:
				ans = 'NO'
				break
	print(ans)


def dfs(n, m, mat, arr1, arr2, count):
	directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
	for (i, j) in directions:
		x = n + i
		y = m + j
		if 0 <= x < len(mat) and 0 <= y < len(mat[0]) and (mat[x][y] == '1') and ((x, y) not in visited):
			arr1.add(x)
			arr2.add(y)
			count[0] += 1
			visited.add((x, y))
			dfs(x, y, mat, arr1, arr2, count)

def dfsUtil(r, c, mat):
	for i in range(r):
		for j in range(c):
			count = [1]
			if mat[i][j] == '1' and (i, j) not in visited:
				arr1 = {i}
				arr2 = {j}
				visited.add((i, j))
				dfs(i, j, mat, arr1, arr2, count)
				if len(arr1) * len(arr2) != count[0]:
					return False
	return True
t = int(input())
for _ in range(t):
	(r, c) = list(map(int, input().split()))
	mat = []
	for i in range(r):
		mat.append(list(input()))
	visited = set()
	if dfsUtil(r, c, mat):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	s = input()
	co = True
	for z in range(n - 1):
		sp = input()
		if co:
			for i in range(m - 1):
				if s[i:i + 2] == '11' and sp[i] != sp[i + 1]:
					co = False
					break
				elif s[i] != s[i + 1] and sp[i:i + 2] == '11':
					co = False
					break
		s = sp
	if co:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for _ in range(n):
		matrix.append(list(map(int, list(input()))))
	done = True
	for (i, row) in enumerate(matrix):
		t_b = None
		for (j, item) in enumerate(row):
			if item == 1:
				if t_b != None:
					if i:
						if i == n - 1:
							if matrix[i - 1][j] != t_b:
								done = False
						elif (matrix[i - 1][j], matrix[i + 1][j]) != t_b:
							done = False
					elif matrix[i + 1][j] != t_b:
						done = False
				elif i:
					if i == n - 1:
						t_b = matrix[i - 1][j]
					else:
						t_b = (matrix[i - 1][j], matrix[i + 1][j])
				else:
					try:
						t_b = matrix[i + 1][j]
					except IndexError:
						pass
			else:
				t_b = None
	if done:
		print('YES')
	else:
		print('NO')


def check(rows):
	previous_row = [0] * m
	for row in rows:
		for i in range(m - 1):
			if previous_row[i] + previous_row[i + 1] == 2 and row[i] + row[i + 1] == 1:
				return 'NO'
			elif previous_row[i] + previous_row[i + 1] == 1 and row[i] + row[i + 1] == 2:
				return 'NO'
		previous_row = row
	return 'YES'
num_tests = int(input())
for _ in range(num_tests):
	(n, m) = [int(num) for num in input().split(' ')]
	rows = []
	for _ in range(n):
		rows.append([int(el) for el in input()])
	print(check(rows))


def solve():
	(n, m) = map(int, input().split())
	arr = []
	flag = 0
	for i in range(n):
		arr.append([int(i) for i in input()])
	for i in range(n - 1):
		for j in range(m - 1):
			if arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1] == 3:
				flag = 1
				break
	print('YES' if not flag else 'NO')
tst = int(input())
for i in range(tst):
	solve()


I = lambda : list(map(int, input()))
for _ in [0] * int(input()):
	(n, m) = map(int, input().split())
	a = []
	e = 1
	for _ in [0] * n:
		a.append(I())
	for i in range(n - 1):
		for j in range(m - 1):
			if a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1] == 3:
				e = 0
				break
	print('YNEOS'[int(e == 0)::2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	for _ in range(n):
		arr = list(map(int, list(input())))
		grid.append(arr)
	ans = 'YES'
	flag = True
	for row in range(n - 1):
		if not flag:
			break
		for col in range(m - 1):
			s = grid[row][col] + grid[row + 1][col] + grid[row][col + 1] + grid[row + 1][col + 1]
			if s == 3:
				flag = False
				ans = 'NO'
				break
	print(ans)


import math
from collections import *

def solve():
	(n, m) = map(int, input().split())
	a = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		s = input()
		for j in range(m):
			a[i][j] = int(s[j])
	for i in range(n - 1):
		for j in range(m - 1):
			s = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1]
			if s == 3:
				print('NO')
				return
	print('YES')
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	table = []
	for i in range(n):
		temp = input()
		table.append(temp)
	ans = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			count = 0
			if table[i][j] == '1':
				count += 1
			if table[i + 1][j] == '1':
				count += 1
			if table[i][j + 1] == '1':
				count += 1
			if table[i + 1][j + 1] == '1':
				count += 1
			if count == 3:
				ans = 'NO'
				break
	print(ans)


for t in range(int(input())):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	arr = [[]] * n
	for i in range(n):
		line = input()
		arr[i] = [0] * m
		for j in range(m):
			arr[i][j] = int(line[j])
	isYes = True
	for i in range(1, n):
		for j in range(1, m):
			if arr[i][j] + arr[i - 1][j] + arr[i - 1][j - 1] + arr[i][j - 1] == 3:
				isYes = False
				break
		if not isYes:
			break
	if isYes:
		print('YES')
	else:
		print('NO')


tc = int(input())
for _ in range(tc):
	(r, c) = map(int, input().split())
	table = [input() for _ in range(r)]
	false = False
	true = True
	flag = false
	for i in range(r):
		for j in range(c):
			if table[i][j] == '0':
				if i > 0 and j > 0 and (table[i - 1][j] == '1') and (table[i - 1][j - 1] == '1') and (table[i][j - 1] == '1'):
					flag = true
				elif i > 0 and j < c - 1 and (table[i - 1][j] == '1') and (table[i - 1][j + 1] == '1') and (table[i][j + 1] == '1'):
					flag = true
				elif i < r - 1 and j < c - 1 and (table[i + 1][j] == '1') and (table[i + 1][j + 1] == '1') and (table[i][j + 1] == '1'):
					flag = true
				elif i < r - 1 and j > 0 and (table[i + 1][j] == '1') and (table[i + 1][j - 1] == '1') and (table[i][j - 1] == '1'):
					flag = true
			if flag:
				break
		if flag:
			break
	if flag:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	t = []
	(n, m) = map(int, input().split())
	s = 0
	for i in range(n):
		a = list((int(char) for char in input()))
		s += sum(a)
		t.append(a)
	if m == 1 or (n == 1 and s >= 1):
		print('YES')
	else:
		ans = 'YES'
		for j in range(n - 1):
			for k in range(m - 1):
				if t[j][k] + t[j + 1][k] + t[j][k + 1] + t[j + 1][k + 1] == 3:
					ans = 'NO'
					break
		print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = [input().strip() for _ in range(n)]
	r = False
	for i in range(n - 1):
		for j in range(m - 1):
			if int(d[i][j]) + int(d[i][j + 1]) + int(d[i + 1][j]) + int(d[i + 1][j + 1]) == 3:
				r = True
				break
		if r:
			break
	print('NO' if r else 'YES')


t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	field = []
	for j in range(n):
		string = [int(k) for k in input()]
		field.append(string)
	is_elegant = True
	for y in range(1, n):
		for x in range(1, m):
			if field[y][x] + field[y - 1][x] + field[y][x - 1] + field[y - 1][x - 1] == 3:
				is_elegant = False
			if not is_elegant:
				break
		if not is_elegant:
			break
	if is_elegant:
		print('YES')
	else:
		print('NO')


def check(n, m, a):
	for i in range(n - 1):
		for j in range(m - 1):
			s = sum(map(int, (a[i][j], a[i][j + 1], a[i + 1][j], a[i + 1][j + 1])))
			if s == 3:
				print('NO')
				return
	print('YES')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[i for i in input()] for _ in range(n)]
	check(n, m, a)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	d = {'0': 0, '1': 1}
	for i in range(n):
		a.append(input())
	ans = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			if d[a[i][j]] + d[a[i][j + 1]] + d[a[i + 1][j]] + d[a[i + 1][j + 1]] == 3:
				ans = 'NO'
	print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	ans = 'YES'
	a = []
	for i in range(n):
		a.append(input())
	for i in range(1, n):
		for j in range(m - 1):
			if a[i][j] == '1' and (a[i - 1][j] == '1' and a[i][j + 1] == '0' and (a[i - 1][j + 1] == '1') or (a[i - 1][j] == '0' and a[i][j + 1] == '1' and (a[i - 1][j + 1] == '1'))):
				ans = 'NO'
				break
		if ans == 'NO':
			break
	if ans == 'YES':
		for i in range(n):
			a[i] = a[i][::-1]
		for i in range(1, n):
			for j in range(m - 1):
				if a[i][j] == '1' and (a[i - 1][j] == '1' and a[i][j + 1] == '0' and (a[i - 1][j + 1] == '1') or (a[i - 1][j] == '0' and a[i][j + 1] == '1' and (a[i - 1][j + 1] == '1'))):
					ans = 'NO'
					break
			if ans == 'NO':
				break
	print(ans)


def result():
	(n, m) = map(int, input().split())
	table = [None] * n
	for i in range(n):
		a = input()
		a = list(a)
		table[i] = a
	flag = 'YES'
	for i in range(1, n):
		for j in range(1, m):
			if int(table[i - 1][j]) + int(table[i][j]) + int(table[i][j - 1]) + int(table[i - 1][j - 1]) == 3:
				flag = 'NO'
	return flag
t = int(input())
for i in range(t):
	print(result())


def pro(arr):
	n = len(arr)
	m = len(arr[0])
	for i in range(n):
		for j in range(m):
			c = 0
			if arr[i][j]:
				c += 1
			if i + 1 < n and arr[i + 1][j]:
				c += 1
			if j + 1 < m and arr[i][j + 1]:
				c += 1
			if i + 1 < n and j + 1 < m and arr[i + 1][j + 1]:
				c += 1
			if c == 3:
				print('NO')
				return
	print('YES')
n = int(input())
for i in range(n):
	(n, m) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(list(map(int, list(input()))))
	pro(arr)


def solve():
	for i in range(n - 1):
		for j in range(m - 1):
			s = arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1]
			if s == 3:
				return 'NO'
	return 'YES'
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	arr = []
	for i in range(n):
		arr.append([int(x) for x in input().strip()])
	print(solve())


import sys
ttime = int(input())
for ccount in range(ttime):
	(n, m) = map(int, sys.stdin.readline().split())
	board = []
	for i in range(n):
		board.append(input())
	bad = False
	for i in range(n - 1):
		for j in range(m - 1):
			if (board[i][j] == '1') + (board[i + 1][j] == '1') + (board[i][j + 1] == '1') + (board[i + 1][j + 1] == '1') == 3:
				bad = True
	if bad:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [[int(x) for x in input()] for y in range(n)]
	ok = True
	for i in range(n - 1):
		for j in range(m - 1):
			if a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1] == 3:
				ok = False
	print('YES' if ok else 'NO')


def is_elegant():
	for i in range(n - 1):
		for j in range(m - 1):
			down = {mat[i + 1][j], mat[i + 1][j + 1]}
			cur = {mat[i][j], mat[i][j + 1]}
			if cur == {'1', '0'} and set(down) == {'1', '1'} or (cur == {'1', '1'} and down == {'1', '0'}):
				return False
	return True
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = [list(input()) for i in range(n)]
	print(['NO', 'YES'][is_elegant()])


import sys
import collections
import itertools
import heapq
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
R = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, R().split())
mod = 1000000007
for _ in range(int(R())):
	(N, M) = MIS()
	L = []
	for _ in range(N):
		L.append(list(map(int, list(R()))))
	flag = 1
	for i in range(N - 1):
		for j in range(M - 1):
			cnt = L[i][j] + L[i][j + 1] + L[i + 1][j] + L[i + 1][j + 1]
			if cnt == 3:
				flag = 0
				break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for case in range(t):
	(n, m) = map(int, input().split())
	M = []
	r = []
	for i in range(n):
		M.append(input())
		r.append([])
		now = 0
		sta = 0
		for j in range(m):
			if M[-1][j] == '1' and now == 0:
				now = 1
				sta = j
			if M[-1][j] == '0' and now == 1:
				now = 0
				end = j - 1
				r[-1].append((sta, end))
		if now == 1:
			end = m - 1
			r[-1].append((sta, end))
	flag = True
	for i in range(n - 1):
		a = 0
		b = 0
		while a < len(r[i]) and b < len(r[i + 1]) and flag:
			if r[i][a][1] < r[i + 1][b][0]:
				a += 1
			elif r[i][a][0] > r[i + 1][b][1]:
				b += 1
			elif r[i][a] == r[i + 1][b]:
				a += 1
				b += 1
			else:
				flag = False
		if not flag:
			break
	print('YES' if flag else 'NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for w in range(n):
		row = list(map(int, input()))
		mat.append(row)
	stop = 0
	for i in range(n - 1):
		for j in range(m - 1):
			if mat[i][j] + mat[i + 1][j] == 2 and mat[i][j + 1] + mat[i + 1][j + 1] == 1:
				stop = 1
				break
			if mat[i][j] + mat[i + 1][j] == 1 and mat[i][j + 1] + mat[i + 1][j + 1] == 2:
				stop = 1
				break
		if stop == 1:
			break
	for i in range(m - 1):
		for j in range(n - 1):
			if mat[j][i] + mat[j][i + 1] == 2 and mat[j + 1][i] + mat[j + 1][i + 1] == 1:
				stop = 1
				break
			if mat[j][i] + mat[j][i + 1] == 1 and mat[j + 1][i] + mat[j + 1][i + 1] == 2:
				stop = 1
				break
		if stop == 1:
			break
	if stop == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	m = inputs[1]
	grid = []
	i = 0
	for i in range(0, n):
		grid.append([num for num in input()])
	i = 0
	flag = 0
	for i in range(0, n):
		for j in range(0, m):
			if grid[i][j] == '0':
				try:
					if i + 1 >= 0 and j + 1 >= 0:
						if grid[i + 1][j] == '1' and grid[i][j + 1] == '1' and (grid[i + 1][j + 1] == '1'):
							flag = 1
							break
				except IndexError:
					pass
				try:
					if i + 1 >= 0 and j - 1 >= 0:
						if grid[i + 1][j] == '1' and grid[i][j - 1] == '1' and (grid[i + 1][j - 1] == '1'):
							flag = 1
							break
				except IndexError:
					pass
				try:
					if i - 1 >= 0 and j + 1 >= 0:
						if grid[i - 1][j] == '1' and grid[i][j + 1] == '1' and (grid[i - 1][j + 1] == '1'):
							flag = 1
							break
				except IndexError:
					pass
				try:
					if i - 1 >= 0 and j - 1 >= 0:
						if grid[i - 1][j] == '1' and grid[i][j - 1] == '1' and (grid[i - 1][j - 1] == '1'):
							flag = 1
							break
				except IndexError:
					pass
		if flag == 1:
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')


def find_cube(ara, x, y):
	for i in range(0, x - 1):
		for j in range(y - 1):
			num = int(ara[i][j]) + int(ara[i + 1][j + 1]) + int(ara[i][j + 1]) + int(ara[i + 1][j])
			if num == 3:
				return False
	return True
t = int(input())
ara = list()
for l in range(t):
	x = input()
	x = x.split(' ')
	y = int(x[1])
	x = int(x[0])
	for i in range(x):
		temp = input()
		ara.append(temp)
	if x > 1 and y > 1:
		sw = find_cube(ara, x, y)
		if sw:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')
	ara.clear()


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, m) = map(int, input().split())
	table = []
	for i in range(n):
		s = input()[:m]
		table.append(list(s))
	for i in range(n - 1):
		for j in range(m - 1):
			if int(table[i][j]) + int(table[i + 1][j]) + int(table[i][j + 1]) + int(table[i + 1][j + 1]) == 3:
				print('NO')
				return
	print('YES')
t = int(input())
while t != 0:
	solve()
	t -= 1


def pr(a):
	for i in range(n - 1):
		for j in range(m - 1):
			s = int(a[i][j]) + int(a[i][j + 1]) + int(a[i + 1][j]) + int(a[i + 1][j + 1])
			if s == 3:
				return 'NO'
	return 'YES'
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(str(input()))
	print(pr(a))


s = []
t = int(input())
for test in range(t):
	tabella = []
	v = 0
	n_m = input().split()
	n = int(n_m[0])
	m = int(n_m[-1])
	for row in range(n):
		riga = input()
		riga_da_appendere = []
		for c in riga:
			riga_da_appendere.append(int(c))
		tabella.append(riga_da_appendere)
	for i in range(n - 1):
		for j in range(m - 1):
			somma = tabella[i][j] + tabella[i][j + 1] + tabella[i + 1][j] + tabella[i + 1][j + 1]
			if somma == 3:
				v = -1
	if v == -1:
		s.append('NO')
	else:
		s.append('YES')
for ss in s:
	print(ss)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		temp = list(input())
		l.append(temp)
	key = 0
	for i in range(n):
		for j in range(m):
			if l[i][j] == '0':
				if j - 1 >= 0 and i - 1 >= 0:
					if l[i - 1][j] == '1' and l[i][j - 1] == '1' and (l[i - 1][j - 1] == '1'):
						key = 1
						break
				if j + 1 < m and i - 1 >= 0:
					if l[i - 1][j] == '1' and l[i][j + 1] == '1' and (l[i - 1][j + 1] == '1'):
						key = 1
						break
				if j + 1 < m and i + 1 < n:
					if l[i + 1][j] == '1' and l[i][j + 1] == '1' and (l[i + 1][j + 1] == '1'):
						key = 1
						break
				if j - 1 >= 0 and i + 1 < n:
					if l[i + 1][j] == '1' and l[i][j - 1] == '1' and (l[i + 1][j - 1] == '1'):
						key = 1
						break
	if key:
		print('NO')
	else:
		print('YES')


def task():
	(n, m) = map(int, input().split())
	matrix = []
	for _ in range(n):
		matrix.append(input())
	result = True
	for i in range(n - 1):
		for j in range(m - 1):
			sum = int(matrix[i][j]) + int(matrix[i + 1][j]) + int(matrix[i][j + 1]) + int(matrix[i + 1][j + 1])
			if sum == 3:
				result = False
				break
	if result:
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	task()


def solve(m, n, s):
	res = 'YES'
	a = 0
	for i in range(1, m):
		for j in range(1, n):
			a = int(s[i][j]) + int(s[i - 1][j]) + int(s[i][j - 1]) + int(s[i - 1][j - 1])
			if a == 3:
				print('NO')
				return
	print(res)
	return
test = int(input())
for te in range(0, test):
	(m, n) = list(map(int, input().split()))
	s = []
	for i in range(0, m):
		s.append(input())
	solve(m, n, s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = []
	for i in range(n):
		A.append(input())
	answer = 'YES'
	for i in range(n):
		for j in range(m):
			if A[i][j] == '0':
				if i != n - 1 and j != m - 1 and (A[i + 1][j + 1] == A[i][j + 1] == A[i + 1][j] == '1'):
					answer = 'NO'
				elif i != 0 and j != 0 and (A[i - 1][j - 1] == A[i][j - 1] == A[i - 1][j] == '1'):
					answer = 'NO'
				elif i != n - 1 and j != 0 and (A[i + 1][j - 1] == A[i][j - 1] == A[i + 1][j] == '1'):
					answer = 'NO'
				elif i != 0 and j != m - 1 and (A[i - 1][j + 1] == A[i - 1][j] == A[i][j + 1] == '1'):
					answer = 'NO'
	print(answer)


t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append([int(j) for j in input()])
	s = 0
	x = 0
	for i in range(1, n):
		for j in range(1, m):
			s = a[i][j] + a[i - 1][j - 1] + a[i - 1][j] + a[i][j - 1]
			if s == 3:
				x = 1
				break
	if x == 1:
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	g = []
	for i in range(n):
		g.append(input())
	ans = 'YES'
	if n == 1 == m:
		print(ans)
		continue
	for (x, y) in zip(g, g[1:]):
		for (a, b, c, d) in zip(x, x[1:], y, y[1:]):
			if int(a) + int(b) + int(c) + int(d) == 3:
				ans = 'NO'
				break
		if ans == 'NO':
			break
	print(ans)


for i in range(int(input())):
	(n, m) = list(map(int, input().split(' ')))
	arr = []
	for i in range(n):
		temp = []
		for i in input():
			temp.append(int(i))
		arr.append(temp)
	res = 'YES'
	for i in range(n):
		for j in range(m):
			try:
				count = arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i][j]
				if count == 3:
					res = 'NO'
			except:
				pass
	print(res)


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	L = []
	for i in range(n):
		L.append(list(map(int, list(input()))))
	flag = True
	if n == 1 or m == 1:
		print('YES')
		continue
	for i in range(n):
		z = L[i]
		j = 0
		while j < m:
			if z[j] == 0:
				j += 1
				continue
			else:
				k = j
				while k + 1 < m:
					if z[k + 1] == 1:
						k += 1
						continue
					else:
						break
				if i == 0:
					if L[i + 1][j:k + 1] != [0 for i in range(k - j + 1)] and L[i + 1][j:k + 1] != [1 for i in range(k - j + 1)]:
						flag = False
						break
				elif i == n - 1:
					if L[i - 1][j:k + 1] != [0 for i in range(k - j + 1)] and L[i - 1][j:k + 1] != [1 for i in range(k - j + 1)]:
						flag = False
						break
				else:
					if L[i + 1][j:k + 1] != [0 for i in range(k - j + 1)] and L[i + 1][j:k + 1] != [1 for i in range(k - j + 1)]:
						flag = False
						break
					if L[i - 1][j:k + 1] != [0 for i in range(k - j + 1)] and L[i - 1][j:k + 1] != [1 for i in range(k - j + 1)]:
						flag = False
						break
				j = k + 1
		if flag == False:
			break
	if flag == False:
		print('NO')
	else:
		print('YES')


import os
import sys
import os.path
from math import *
from copy import deepcopy
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
	sys.stdout = open('ot.txt', 'w')

def main():
	for ttt in range(int(input())):
		(n, m) = map(int, input().split())
		mat = []
		for i in range(n):
			s = input()
			mat.append(s)
		ans = 1
		for i in range(n - 1):
			for j in range(m - 1):
				if int(mat[i][j]) + int(mat[i + 1][j]) + int(mat[i][j + 1]) + int(mat[i + 1][j + 1]) == 3:
					ans = 0
		if ans == 0:
			print('NO')
		else:
			print('YES')
main()


for _ in range(int(input())):
	sq = []
	(n, m) = map(int, input().split())
	for i in range(n):
		sq.append(list(map(int, list(input()))))
	ans = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			if sum(sq[i:i + 2][0][j:j + 2] + sq[i:i + 2][1][j:j + 2]) == 3:
				ans = 'NO'
				break
	print(ans)


def solve():
	(x, y) = map(int, input().split())
	a = []
	ans = 'YES'
	for i in range(x):
		a.append(input())
	check = 0
	for i in range(x - 1):
		for j in range(y - 1):
			check = int(a[i][j]) + int(a[i + 1][j]) + int(a[i][j + 1]) + int(a[i + 1][j + 1])
			if check == 3:
				ans = 'NO'
				break
	print(ans)
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = []
	for i in range(n):
		st = input()
		s.append(st)
	ans = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			if int(s[i][j]) + int(s[i + 1][j]) + int(s[i][j + 1]) + int(s[i + 1][j + 1]) == 3:
				ans = 'NO'
				break
	print(ans)


from math import inf
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(str(input()))
	test = 'YES'
	for i in range(n - 1):
		for j in range(m - 1):
			if int(l[i][j]) + int(l[i][j + 1]) + int(l[i + 1][j]) + int(l[i + 1][j + 1]) == 3:
				test = 'NO'
	print(test)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for j in range(n):
		s = input()
		lst = []
		for k in s:
			lst.append(int(k))
		matrix.append(lst)
	err = 0
	for a in range(n - 1):
		for b in range(m - 1):
			c1 = 0
			if matrix[a][b] == 1:
				c1 += 1
			if matrix[a][b + 1] == 1:
				c1 += 1
			if matrix[a + 1][b] == 1:
				c1 += 1
			if matrix[a + 1][b + 1] == 1:
				c1 += 1
			if c1 == 3:
				err += 1
				break
	if err > 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	(rows, cols) = map(int, input().split())
	row_wise = []
	col_wise = []
	for i in range(rows):
		row_wise.append(input())
	for i in range(cols):
		string = ''
		for j in range(rows):
			string += row_wise[j][i]
		col_wise.append(string)
	output = 'ok'
	for i in range(rows - 1):
		if output != 'ok':
			break
		for j in range(cols - 1):
			if (row_wise[i][j] + row_wise[i][j + 1] + row_wise[i + 1][j] + row_wise[i + 1][j + 1]).count('0') == 1:
				output = 'YES'
				break
	if output == 'ok':
		print('YES')
	else:
		print('NO')


x = int(input())
for k in range(x):
	(a, b) = list(map(int, input().split()))
	c = []
	for ll in range(a):
		y = input()
		flag = 0
		d = []
		count1 = 0
		count2 = 0
		for kk in range(b):
			if flag == 0 and y[kk] == '1':
				count1 += 1
				d.append(count1)
				count2 = 0
			else:
				count1 = 0
				flag = 0
				d.append(count2)
		c.append(d)
	ans = 1
	for ll in range(1, a):
		ii = 0
		while ii < b:
			if c[ll][ii] == c[ll - 1][ii]:
				ans = 1
				ii += 1
			elif c[ll][ii] == 0 and c[ll - 1][ii] == 1:
				z = ii
				while z < b and c[ll - 1][z] != 0:
					if c[ll][z] == 0:
						ans = 1
					else:
						ans = 0
						break
					z += 1
				ii = z
			elif c[ll - 1][ii] == 0 and c[ll][ii] == 1:
				z = ii
				while z < b and c[ll][z] != 0:
					if c[ll - 1][z] == 0:
						ans = 1
					else:
						ans = 0
						break
					z += 1
				ii = z
			else:
				ans = 0
				break
		if ans == 0:
			break
	if ans == 1:
		print('YES')
	else:
		print('NO')


def IsElegant(lst):
	elegant = True
	if len(lst) > 1 and len(lst[0]) > 1:
		for i in range(len(lst) - 1):
			for j in range(len(lst[i]) - 1):
				s3 = int(lst[i][j]) + int(lst[i + 1][j]) + int(lst[i][j + 1]) + int(lst[i + 1][j + 1])
				if s3 == 3:
					elegant = False
	return elegant
tests = int(input())
ans = []
for i in range(tests):
	(n, m) = map(int, input().split())
	lst = []
	for j in range(n):
		lst.append(str(input()))
	ans.append(IsElegant(lst))
for i in range(tests):
	if ans[i] == True:
		print('YES')
	else:
		print('NO')