Read problems statements in [Hindi], [Mandarin Chinese], [Vietnamese], and [Bengali] as well.

You are given a grid with $N$ rows and $M$ columns, where each cell contains either '0' or '1'. 

Find out whether all the cells containing '1'-s form a rectangle, I.e, is there a rectangular contiguous subgrid such that every cell within it is a '1', and all the cells containing '1'-s are within this subgrid.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains a single string with length $M$ describing the $i$-th row of the grid.

------  Output ------
For each test case, print a single line containing the string "YES" if the connected component of '1'-s is a rectangle or "NO" if it is not.

Note: The output is case-insensitive ― each letter may be printed in upper case or lower case.

------  Constraints  ------
$1 ≤ T ≤ 1000$
$1 ≤ N, M ≤ 500$
Sum of $N*M$ over all tests is atmost $1.5*10^{6}$
Each string contains only characters '0' and '1'
It is guaranteed that grid contains at least a single '1'

----- Sample Input 1 ------ 
3
3 3
010
111
010
4 4
0000
0110
1110
1100
3 3
011
011
000
----- Sample Output 1 ------ 
NO
NO
YES
----- explanation 1 ------ 
Example case 1: The minimal rectangle which covers all '1'-s also covers $4$ cells which contain '0'-s.

Example case 2: The minimal rectangle which covers all '1'-s also covers $2$ cells which contain '0'-s.

Example case 3: We can form a minimal rectangle with side length $2$ which covers all cells containing '1'-s and none of the cells containing '0'-s.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	r = '0'
	l = []
	for j in range(n):
		x = input()
		for k in range(m):
			if x[k] == '1':
				r += str(k)
		if r != '0':
			l.append(int(r))
		r = '0'
	print('YES' if max(l) - min(l) == 0 else 'NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	trial = '0'
	lst = []
	for _ in range(n):
		x = input()
		for i in range(m):
			if x[i] == '1':
				trial += str(i)
		if trial != '0':
			lst.append(int(trial))
		trial = '0'
	if max(lst) - min(lst) == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		temp = str(input())
		l.append(temp)
	output = []
	for i in range(n):
		for j in range(m):
			if '1' not in l[i]:
				break
			if l[i][j] == '1':
				start = j
				j = j + 1
				count = 1
				try:
					while l[i][j] == '1':
						count = count + 1
						j = j + 1
				except IndexError:
					pass
				output.append((start, count))
				break
	output = set(output)
	if len(output) == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	left = set()
	right = set()
	cols = []
	for i in range(n):
		ll = l[i].find('1')
		rr = l[i].rfind('1')
		if ll != -1:
			left.add(ll)
			right.add(rr)
			cols.append(i)
	if len(left) > 1 or len(right) > 1:
		print('NO')
	else:
		m = list(left)[0]
		M = list(right)[0]
		cnt = 0
		for i in range(cols[0], cols[-1] + 1):
			cnt += l[i][m:M + 1].count('0')
		if cnt == 0:
			print('YES')
		else:
			print('NO')


def rect(arr, n=0, m=0):
	min_row = n
	min_col = m
	max_row = max_col = -1
	for i in range(n):
		for j in range(m):
			if arr[i][j]:
				min_row = min(min_row, i)
				min_col = min(min_col, j)
				max_row = max(max_row, i)
				max_col = max(max_col, j)
	for i in range(min_row, max_row + 1):
		for j in range(min_col, max_col + 1):
			if not arr[i][j]:
				return 'NO'
	return 'YES'
T = int(input())
for tc in range(T):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		row = [int(i) for i in input()]
		l.append(row)
	print(rect(l, n, m))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(input())
	h = []
	k = []
	for i in range(n):
		p = mat[i].find('1')
		h.append(p)
		y = mat[i].rfind('1')
		k.append(y)
	c = 0
	x = abs(max(k) - max(h)) + 1
	for i in range(len(h)):
		if k[i] != -1 and h[i] != -1:
			if x * '1' in mat[i]:
				pass
			else:
				c = 1
	for i in range(len(h)):
		if h[i] == max(h) and k[i] == max(k):
			pass
		elif h[i] == -1 and k[i] == -1:
			pass
		else:
			c = 1
			break
	if c == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = tuple(map(int, input().split()))
	value = 0
	ans = 'YES'
	for i in range(n):
		x = int(input(), 2)
		if x != 0:
			if value != 0:
				if x != value:
					ans = 'NO'
			else:
				value = x
	print(ans)


from collections import defaultdict
t = int(input())
while t:
	(n, m) = map(int, input().split())
	l = []
	d = defaultdict(list)
	for i in range(n):
		x = list(map(int, input()))
		for j in range(m):
			if x[j] == 1:
				d[i].append(j)
	l = list(d.keys())
	k = l[0]
	v = d[k]
	flag = 1
	for i in d.keys():
		if d[i] != v or i != k:
			flag = 0
			break
		k += 1
	if flag == 1:
		print('YES')
	else:
		print('NO')
	t -= 1


import re
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		A.append(input())
	A = set(A)
	regex = re.compile('^0*$')
	f = [i for i in A if not regex.match(i)]
	if len(f) == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	mat = []
	for _ in range(r):
		mat.append(list(input()))
	while True:
		if all(list(map(lambda ele: ele == '0', mat[r - 1]))):
			r -= 1
		else:
			break
	(fi, fj, lj) = (-1, -1, -1)
	fl = True
	for i in range(r):
		for j in range(c):
			if i == fi and mat[i][j] == '1':
				lj = j
			if fi == -1 and mat[i][j] == '1':
				(fi, fj) = (i, j)
				lj = fj
			elif j >= fj and j <= lj:
				if mat[i][j] != '1':
					fl = False
					break
			elif mat[i][j] == '1':
				fl = False
				break
	print('YES' if fl else 'NO')


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
for _ in range(int(input())):
	(n, m) = inp()
	mat = []
	for _i in range(n):
		mat.append([int(s) for s in list(input())])
	max_x = -1
	min_x = n + 1
	max_y = -1
	min_y = m + 1
	cnt1 = 0
	for i in range(n):
		for j in range(m):
			if mat[i][j] == 1:
				max_x = max(max_x, i)
				min_x = min(min_x, i)
				max_y = max(max_y, j)
				min_y = min(min_y, j)
	cnt2 = 0
	flag = True
	for i in range(min_x, max_x + 1):
		for j in range(min_y, max_y + 1):
			if mat[i][j] == 1:
				pass
			else:
				flag = False
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	flag = 0
	arr = []
	for i in range(n):
		j = list(input())
		arr.append(j)
	m1 = m2 = 501
	m3 = m4 = -1
	ct = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '1':
				m1 = min(m1, i)
				m2 = min(m2, j)
				m3 = max(m3, i)
				m4 = max(m4, j)
				ct += 1
	for i in range(m1, m3 + 1):
		for j in range(m2, m4 + 1):
			if arr[i][j] == '0':
				flag = 1
				break
			else:
				ct -= 1
		if flag:
			break
	if flag or ct:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		temp = [int(x) for x in input()]
		mat.append(temp)
	col_min = m + 1
	col_max = -1
	row_min = n + 1
	row_max = -1
	for i in range(n):
		for j in range(m):
			if mat[i][j] == 1:
				row_min = min(row_min, i)
				row_max = max(row_max, i)
				col_min = min(col_min, j)
				col_max = max(col_max, j)
	flag = 0
	for i in range(row_min, row_max + 1):
		if flag == 1:
			break
		for j in range(col_min, col_max + 1):
			if mat[i][j] == 0:
				print('NO')
				flag = 1
				break
	if flag == 0:
		print('YES')


def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		l = []
		for _ in range(n):
			el = '0'
			r = input()
			for j in range(m):
				if r[j] == '1':
					el += str(j + 1)
			if el != '0':
				l.append(int(el))
		if max(l) == min(l):
			print('YES')
		else:
			print('NO')
main()


t = int(input())
lst = []
trial = '0'
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	for o in range(n):
		grid_num = input()
		for p in range(m):
			if grid_num[p] == '1':
				trial += str(p)
		if trial != '0':
			lst.append(int(trial))
		trial = '0'
	if max(lst) - min(lst) == 0:
		print('YES')
	else:
		print('NO')
	lst = []


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, m) = mp()
	x = [input() for i in range(n)]
	l = [int(i) for i in x if int(i)]
	pr('YES' if min(l) == max(l) else 'NO')
for _ in range(inp()):
	solve()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, m) = mp()
	l = [st() for i in range(n)]
	(F, L) = (set(), set())
	(start, end) = (-1, -1)
	for i in range(n):
		(first, last) = (-1, -1)
		for j in range(m):
			if l[i][j] == '1':
				if first == -1:
					first = j
				if start == -1:
					start = i
				end = i
				last = j
		if first != -1:
			F.add(first)
			L.add(last)
		if len(F) > 1 or len(L) > 1:
			pr('NO')
			return
	(a, b) = (list(F)[0], list(L)[0])
	for i in range(a, b + 1):
		for j in range(start, end + 1):
			if l[j][i] == '0':
				pr('NO')
				return
	pr('YES')
for _ in range(inp()):
	solve()


t = int(input())
for case in range(t):
	(n, m) = [int(i) for i in input().split()]
	a = [[int(i) for i in input()] for j in range(n)]
	x1 = n + 1
	y1 = m + 1
	x2 = y2 = -1
	c = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				c += 1
				if i <= x1 and j <= y1:
					x1 = i
					y1 = j
				if i >= x2 and j >= y2:
					x2 = i
					y2 = j
	if (x2 - x1 + 1) * (y2 - y1 + 1) == c:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	(N, M) = list(map(int, input().strip().split()))
	ans = []
	for row in range(N):
		rec = '0'
		grid = input().strip()
		for idx in range(len(grid)):
			if grid[idx] == '1':
				rec += str(idx)
		if rec != '0':
			ans.append(int(rec))
	if max(ans) - min(ans) == 0:
		print('YES')
	else:
		print('NO')


from math import *
from statistics import mode
from functools import reduce
from sys import stdin
import heapq
from collections import deque

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

def graph(vertex):
	return [[] for i in range(vertex + 1)]

def lcm(a, b):
	return a * b // gcd(a, b)

def most_common(List):
	return mode(List)

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def prime_factors(n):
	(i, factors) = (2, [])
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def kadane(a, size):
	max_so_far = curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def isPowerOf2(x):
	return x and (not x & x - 1)

def isPerfectSquare(n):
	return pow(floor(sqrt(n)), 2) == n

def binarySearch(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1
for t in range(int(input())):
	(N, M) = map(int, input().split())
	ast = None
	ans = None
	for i in range(N):
		s = input()
		if int(s):
			if ast is None:
				ast = s
				ans = 'YES'
			elif s != ast:
				ans = 'NO'
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	list1 = []
	for i in range(n):
		a = int(input())
		if a > 0:
			list1.append(a)
	if max(list1) - min(list1) == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	c = 0
	for i in range(n):
		a.append(input())
	minn = m - 1
	maxx = 0
	for i in range(0, n):
		for j in range(0, m):
			if a[i][j] == '1':
				c += 1
				minn = min(j, minn)
				maxx = max(maxx, j)
	col = maxx - minn + 1
	minn = n - 1
	maxx = 0
	for i in range(0, m):
		for j in range(0, n):
			if a[j][i] == '1':
				minn = min(j, minn)
				maxx = max(j, maxx)
	row = maxx - minn + 1
	if c == row * col:
		print('YES')
	else:
		print('NO')


from math import *
for u in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	f = 0
	for i in range(n):
		l.append(input())
	(a, b, c, d) = (-inf, inf, -inf, inf)
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				b = min(b, i)
				a = max(b, i)
				d = min(d, j)
				c = max(c, j)
	for i in range(b, a + 1):
		for j in range(d, c + 1):
			if l[i][j] == '0':
				f = 1
				break
	if f == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = []
	cmn = m + 1
	cmx = -1
	rmn = n + 1
	rmx = -1
	for i in range(n):
		a.append(input())
		for j in range(m):
			if a[i][j] == '1':
				if cmn > j:
					cmn = j
				if cmx < j:
					cmx = j
				if rmn > i:
					rmn = i
				if rmx < i:
					rmx = i
	b = False
	for i in range(rmn, rmx + 1):
		for j in range(cmn, cmx + 1):
			if a[i][j] != '1':
				b = True
				break
		if b:
			break
	if b:
		print('NO')
	else:
		print('YES')


t = int(input())
test = '0'
lst = []
for _ in range(t):
	(n, m) = map(int, input().split())
	for o in range(n):
		line = input()
		for p in range(m):
			if line[p] == '1':
				test += str(p)
		if test != '0':
			lst.append(int(test))
		test = '0'
	if max(lst) - min(lst) == 0:
		print('YES')
	else:
		print('NO')
	lst = []


t = int(input())
o = []
while t > 0:
	(n, m) = input().split()
	n = int(n)
	n1 = n
	m = int(m)
	l = []
	t += -1
	while n > 0:
		n += -1
		s = input()
		s = s[0:m]
		l.append(s)
	i = 0
	q = True
	j2 = m - 1
	while i < n1 and q == True:
		j = 0
		while j < m and q:
			if l[i][j] == '1':
				q = False
				j2 = j
				break
			else:
				j += 1
		if q:
			i += 1
		else:
			break
	p = True
	a = n1 - 1
	b1 = 0
	while a >= 0 and p == True:
		b = m - 1
		while b >= 0:
			if l[a][b] == '1':
				b1 = b
				p = False
				break
			else:
				b += -1
		if p:
			a += -1
		else:
			break
	p = 0
	c = True
	while p < n1 and c:
		q = 0
		while q < m and c:
			if p < i:
				if l[p][q] == '1':
					c = False
					break
			elif i <= p <= a and (q < j2 or q > b1):
				if l[p][q] == '1':
					c = False
					break
			elif i <= p <= a and j2 <= q <= b1:
				if l[p][q] == '0':
					c = False
					break
			elif p > a:
				if l[p][q] == '1':
					c = False
					break
			q += 1
		if c:
			p += 1
		else:
			break
	if c:
		o.append('YES')
	if not c:
		o.append('NO')
for x in o:
	print(x)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	mat = []
	ones = []
	for i in range(n):
		r = str(input())
		mat.append(r)
		if '1' in r:
			ones.append(i)
	no = False
	for i in range(1, len(ones)):
		if ones[i] - ones[i - 1] > 1:
			no = True
			break
	if not no:
		ones = {mat[i] for i in ones}
		if len(ones) != 1:
			no = True
	if no:
		print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a += [input()]
	(u, d, l, r) = (-1, -1, -1, -1)
	res = 'YES'
	for i in range(n):
		if '1' in a[i]:
			d = i
			if u == -1:
				u = i
	if u == -1:
		print(res)
	else:
		for i in range(m):
			if a[u][i] == '1':
				if l == -1:
					l = i
				r = i
		s = '0' * l + '1' * (r - l + 1) + '0' * (m - r - 1)
		for i in range(u, d + 1):
			if a[i] != s:
				res = 'NO'
				break
		print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	(minx, miny, maxx, maxy) = (1000, 1000, -1000, -1000)
	for i in range(n):
		s = input()
		a.append(s)
		for j in range(m):
			if s[j] == '1':
				if j < minx:
					minx = j
				if i < miny:
					miny = i
				if j > maxx:
					maxx = j
				if i > maxy:
					maxy = i
	flag = True
	for i in range(miny, maxy + 1):
		for j in range(minx, maxx + 1):
			if a[i][j] == '0':
				flag = False
				break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	a = [int(x) for x in input().split()]
	n = a[0]
	m = a[1]
	mat = []
	c = 0
	minX = float('inf')
	maxX = float('-inf')
	minY = float('inf')
	maxY = float('-inf')
	for j in range(n):
		mat.append(list(input()))
	for j in range(n):
		for k in range(m):
			if mat[j][k] == '1':
				c += 1
				minX = min(minX, j)
				maxX = max(maxX, j)
				minY = min(minY, k)
				maxY = max(maxY, k)
	if c == (maxX - minX + 1) * (maxY - minY + 1):
		print('YES')
	else:
		print('NO')


def maxHist(row):
	res = []
	top = maxx = area = i = 0
	while i < len(row):
		if len(res) == 0 or row[res[-1]] <= row[i]:
			res.append(i)
			i += 1
		else:
			top = row[res.pop()]
			area = top * i
			if len(res):
				area = top * (i - res[-1] - 1)
			maxx = max(area, maxx)
	while len(res):
		top = row[res.pop()]
		area = top * i
		if len(res):
			area = top * (i - res[-1] - 1)
		maxx = max(area, maxx)
	return maxx

def check(mat):
	res = maxHist(mat[0])
	for i in range(1, len(mat)):
		for j in range(len(mat[i])):
			if mat[i][j]:
				mat[i][j] += mat[i - 1][j]
		res = max(res, maxHist(mat[i]))
	return res
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	mat = []
	count1 = 0
	for i in range(r):
		a = []
		for j in input():
			if j == '1':
				count1 += 1
			a.append(int(j))
		mat.append(a)
	res = check(mat)
	if res == count1:
		print('YES')
	else:
		print('NO')


n = 3
m = 3
a = ['011', '011', '000']
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = []
	z = '0' * m
	for i in range(n):
		a.append(input())
	st = False
	ed = False
	ans = 'YES'
	for i in range(n):
		r = a[i]
		if ed and r != z:
			ans = 'NO'
			break
		if st:
			if r == z:
				ed = True
			if ed == False and r != pat:
				ans = 'NO'
				break
		if st is False and r != z:
			st = True
			pat = r
	if not st:
		ans = 'NO'
	print(ans)


for z in range(int(input())):
	(r, c) = map(int, input().split())
	count = 0
	f = 0
	m = []
	for i in range(r):
		l = input().strip()
		for j in range(c):
			if l[j] == '1':
				count += 1
				if f == 0:
					(sr, sc) = (i, j)
					f += 1
				else:
					(er, ec) = (i, j)
		m.append(l)
	if count == 1:
		print('YES')
	elif er < sr or ec < sc:
		print('NO')
	else:
		f = 1
		for i in range(r):
			for j in range(c):
				if i >= sr and i <= er and (j >= sc) and (j <= ec):
					if m[i][j] == '0':
						print('NO')
						f = 0
						break
				elif m[i][j] == '1':
					f = 0
					print('NO')
					break
			if f == 0:
				break
		else:
			print('YES')


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = []
	a1 = [0] * n
	colMx = -1
	colMn = n + 1
	rowMn = m + 1
	rowMx = -1
	for i in range(n):
		a.append(input())
		for j in range(m):
			if a[i][j] == '1':
				if rowMx < j:
					rowMx = j
				if rowMn > j:
					rowMn = j
				if colMx < i:
					colMx = i
				if colMn > i:
					colMn = i
	flag = False
	for i in range(colMn, colMx + 1):
		for j in range(rowMn, rowMx + 1):
			if a[i][j] != '1':
				flag = True
				break
		if flag:
			break
	if flag:
		print('NO')
	else:
		print('YES')


t = int(input())
for t in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(input())
	a = 0
	b = 0
	m1 = 0
	m2 = 0
	d = 0
	for i in range(n):
		if d == 0:
			if m1 == 0:
				for j in range(m):
					if matrix[i][j] == '1':
						m1 = 1
					if m2 == 0:
						if matrix[i][j] == '1':
							m2 = 1
							a = j
					elif m2 == 1:
						if matrix[i][j] == '0':
							b = j - 1
							m2 = 2
					elif matrix[i][j] == '1':
						d = 1
						m2 = 2
						break
				if m1 == 1:
					if matrix[i][-1] == '1':
						b = m - 1
			else:
				m2 = 0
				for j in range(m):
					if matrix[i][j] == '1':
						m2 = 1
				if m2 == 1:
					for j in range(a):
						if matrix[i][j] == '1':
							d = 1
							break
					for j in range(a, b + 1):
						if matrix[i][j] == '0':
							d = 1
							break
					for j in range(b + 1, m):
						if matrix[i][j] == '1':
							d = 1
							break
	if d == 0:
		print('YES')
	else:
		print('NO')


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


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	(start, stop) = (0, 0)
	c = 0
	rowise = 0
	condition = True
	for j in range(0, n):
		s = input()
		if condition == True:
			if '1' in s and rowise == 0:
				rowise = 1
				for k in range(0, m):
					if s[k] == '1' and c == 0:
						c = 1
						start = k
					elif s[k] == '0' and c == 1:
						c = 2
						stop = k - 1
					elif s[k] == '1' and c == 2:
						condition = False
						break
				if stop == 0:
					stop = m - 1
			elif '1' not in s and rowise == 1:
				rowise = 2
			elif '1' in s and rowise == 2:
				condition = False
				break
			elif '1' in s and rowise == 1:
				for k in range(0, m):
					if (k < start or k > stop) and s[k] != '0':
						condition = False
					elif (k >= start and k <= stop) and s[k] != '1':
						condition = False
	if condition == True:
		print('YES')
	else:
		print('NO')


def ii():
	return int(input().strip())

def si():
	return input().strip()

def mi():
	return map(int, input().strip().split())

def li():
	return list(mi())
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']

def bo(i):
	return ord(i) - ord('a')
t = ii()
for _t in range(t):
	(n, m) = li()
	dx = dict()
	dy = dict()
	mat = list()
	for i in range(n):
		mat.append([int(x) for x in si()])
	for i in range(n):
		tmp = mat[i]
		for j in range(m):
			if tmp[j] == 1:
				if i in dx:
					dx[i].append(j)
				else:
					dx[i] = [j]
				if j in dy:
					dy[j].append(i)
				else:
					dy[j] = [i]
	lt = 0
	lb = 0
	rt = 0
	rb = 0
	tl = 0
	bl = 0
	tr = 0
	br = 0
	for i in range(m):
		if i in dy:
			lt = (dy[i][0], i)
			lb = (dy[i][-1], i)
			break
	for i in range(m - 1, -1, -1):
		if i in dy:
			rt = (dy[i][0], i)
			rb = (dy[i][-1], i)
			break
	for i in range(n):
		if i in dx:
			tl = (i, dx[i][0])
			tr = (i, dx[i][-1])
			break
	for i in range(n - 1, -1, -1):
		if i in dx:
			bl = (i, dx[i][0])
			br = (i, dx[i][-1])
			break
	if (lt[0] == tl[0] and lt[1] == tl[1]) and (lb[0] == bl[0] and lb[1] == bl[1]) and (rt[0] == tr[0] and rt[1] == tr[1]) and (rb[0] == br[0] and rb[1] == br[1]):
		ans = 1
		for i in range(tl[0], lb[0] + 1):
			for j in range(tl[1], tr[1] + 1):
				if mat[i][j] == 0:
					ans = 0
		if ans:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


def rectangle(grid):
	if not grid or not grid[0]:
		return 'NO'
	m = len(grid)
	n = len(grid[0])
	(ul, ur) = ((-1, -1), (-1, -1))
	for i in range(m):
		j = 0
		while j < n:
			if grid[i][j] == 1 and ul == (-1, -1):
				ul = (i, j)
				ll = (i, j)
				while j < n and grid[i][j] == 1:
					ur = (i, j)
					lr = (i, j)
					j += 1
			if j < n and grid[i][j] == 1 and (not ul[1] <= j <= ur[1]):
				return 'NO'
			if j < n and grid[i][j] == 1 and (j == ul[1]):
				ll = (i, j)
				while j < n and grid[i][j] == 1:
					j += 1
				lr = (i, j - 1)
				if ur[1] != lr[1]:
					return 'NO'
			if j < n and grid[i][j] == 1 and (j < ul[1] or j > ur[1] or i < ul[0] or (i > ll[0])):
				return 'NO'
			j += 1
	return 'YES'
t = int(input())
res = []
while t:
	(n, m) = map(int, input().split())
	grid = []
	for _ in range(n):
		row = [int(r) for r in input()]
		grid.append(row)
	t -= 1
	res.append(rectangle(grid))
for r in res:
	print(r)


t = int(input())
for j in range(t):
	(n, m) = map(int, input().split())
	S = []
	zeros = '0' * m
	for k in range(n):
		s = str(input())
		S.append(s)
	SS = list(set(S))
	if len(SS) > 2:
		print('NO')
	elif len(SS) == 2:
		if zeros not in S:
			print('NO')
		else:
			SSS = SS.copy()
			SSS.remove(zeros)
			a = SSS[0]
			indices = [i for (i, x) in enumerate(S) if x == a]
			if max(indices) - min(indices) + 1 == len(indices):
				print('YES')
			else:
				print('NO')
	else:
		a = SS[0]
		if a == zeros:
			print('NO')
		else:
			print('YES')


import sys, collections, operator
from functools import cmp_to_key
from collections import OrderedDict
from itertools import permutations
from math import sqrt

def get_inp():
	return sys.stdin.readline().strip()

def get_inps():
	return sys.stdin.readline().strip().split()

def println(str):
	return sys.stdout.write(str + '\n')

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def power(a, b):
	res = 1
	while b > 0:
		if b & 1 == 1:
			res = res * a
		b = b >> 1
		a = a * a
	return res
try:
	t = int(get_inp())
	while t > 0:
		(n, m) = map(int, get_inps())
		rec = [[i for i in get_inp()] for j in range(n)]
		cones = 0
		for i in range(n):
			for j in range(m):
				if rec[i][j] == '1':
					cones += 1
		for i in range(n):
			f = False
			for j in range(m):
				if rec[i][j] == '1':
					id1 = j
					id2 = 0
					idx = i
					temp = j
					while temp < m and rec[i][temp] == '1':
						temp += 1
					id2 = temp - 1
					f = True
					break
			if f == True:
				break
		c = 0
		for i in range(idx, n):
			if rec[i][id1] == '0':
				break
			for j in range(id1, id2 + 1):
				c += 1
		if c == cones:
			print('YES')
		else:
			print('NO')
		t -= 1
except Exception as e:
	pass


T = int(input())

class Solver:

	def __init__(self):
		for _ in range(T):
			print(self.Solve())

	def Solve(self):
		(N, M) = map(int, input().split(' '))
		g = []
		for _ in range(N):
			row = list(map(int, list(input())))
			row = [0] + row + [0]
			g += [row]
		g = [[0 for _ in range(M + 2)]] + g + [[0 for _ in range(M + 2)]]
		tl = br = None
		cnt1 = 0
		for r in range(1, N + 1):
			for c in range(1, M + 1):
				if g[r][c] == 1:
					cnt1 += 1
				if tl is None:
					if g[r][c] == 1 and g[r - 1][c] == 0 and (g[r - 1][c - 1] == 0) and (g[r][c - 1] == 0):
						tl = (r, c)
				if g[r][c] == 1 and g[r + 1][c] == 0 and (g[r + 1][c + 1] == 0) and (g[r][c + 1] == 0):
					br = (r, c)
		(tlr, tlc) = tl
		(brr, brc) = br
		for r in range(tlr, brr + 1):
			for c in range(tlc, brc + 1):
				if g[r][c] == 0:
					return 'NO'
		return 'YES' if (brr - tlr + 1) * (brc - tlc + 1) == cnt1 else 'NO'
	pass
Solver()


t = int(input())
for t in range(t):
	(p, q) = map(int, input().split())
	x = y = q1 = q2 = 0
	t1 = 0
	for i in range(p):
		s = input()
		if t1 == 0:
			if q1 == 0:
				for j in range(q):
					if s[j] == '1':
						q1 = 1
					if q2 == 0:
						if s[j] == '1':
							q2 = 1
							x = j
					elif q2 == 1:
						if s[j] == '0':
							y = j - 1
							q2 = 2
					elif s[j] == '1':
						t1 = 1
						q2 = 2
						break
				if q1 == 1:
					if s[-1] == '1':
						y = q - 1
			else:
				q2 = 0
				for j in range(q):
					if s[j] == '1':
						q2 = 1
				if q2 == 1:
					for j in range(x):
						if s[j] == '1':
							t1 = 1
							break
					for j in range(x, y + 1):
						if s[j] == '0':
							t1 = 1
							break
					for j in range(y + 1, q):
						if s[j] == '1':
							t1 = 1
							break
	if t1 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = tuple(map(int, input().strip().split()))
	started = False
	exit = False
	fin = []
	for i in range(0, n):
		fin.append(input())
	for i in range(0, n):
		str_ = fin[i]
		if str_ != '0' * m:
			if started == False:
				arr = str_.split('0')
				remove = arr.count('')
				if len(arr) - remove != 1:
					exit = True
					break
				else:
					main_str = str_
					started = True
			elif str_ != main_str:
				exit = True
				break
	if exit == True:
		print('NO')
	else:
		print('YES')


def main():
	for _ in range(int(input())):
		print(find_ans())

def find_ans():
	(ROWS, COLUMNS) = map(int, input().split())
	grid = [input().strip() for i in range(ROWS)]
	bottomright = None
	topleft = None
	for r in range(ROWS):
		for c in range(COLUMNS):
			if grid[r][c] == '1':
				if topleft is None:
					topleft = (r, c)
				bottomright = (r, c)
	if topleft[1] > bottomright[1]:
		return 'NO'
	for r in range(ROWS):
		for c in range(COLUMNS):
			if topleft[0] <= r <= bottomright[0] and topleft[1] <= c <= bottomright[1]:
				if grid[r][c] == '0':
					return 'NO'
			elif grid[r][c] == '1':
				return 'NO'
	return 'YES'
main()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	c = 0
	a = []
	for j in range(n):
		ai = []
		l1 = list(input())
		if l1.count('1') > 0:
			for k in range(len(l1)):
				if l1[k] == '1':
					ai.append(k)
			a.append(ai)
	if a.count(a[0]) == len(a):
		print('YES')
	else:
		print('NO')


def bada_func(main):
	leftflag = 0
	rightflag = 0
	flag = 0
	for i in range(n):
		for j in range(m):
			if main[i][j] == '1' and leftflag == 0:
				l = j
				leftflag = 1
			if main[i][j] == '0' and leftflag == 1 and (rightflag == 0):
				r = j - 1
				rightflag = 1
				flag = 1
			elif leftflag == 1 and rightflag == 0 and (j == m - 1):
				r = j
				rightflag = 1
				flag = 1
			if main[i][j] == '1' and flag == 1:
				if l <= j <= r:
					pass
				else:
					return 'NO'
			elif main[i][j] == '0' and flag == 1 and (j == l):
				flag = 2
			elif main[i][j] == '0' and flag == 1:
				if l <= j <= r:
					return 'NO'
				else:
					pass
			elif main[i][j] == '1' and flag == 2:
				return 'NO'
	if flag < 1:
		return 'NO'
	else:
		return 'YES'
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	main = []
	for i in range(n):
		s = list(input())
		main.append(s)
	print(bada_func(main))


class Rect:

	def maxHist(self, row):
		result = []
		top_val = 0
		max_area = 0
		area = 0
		i = 0
		while i < len(row):
			if len(result) == 0 or row[result[-1]] <= row[i]:
				result.append(i)
				i += 1
			else:
				top_val = row[result.pop()]
				area = top_val * i
				if len(result):
					area = top_val * (i - result[-1] - 1)
				max_area = max(area, max_area)
		while len(result):
			top_val = row[result.pop()]
			area = top_val * i
			if len(result):
				area = top_val * (i - result[-1] - 1)
			max_area = max(area, max_area)
		return max_area

	def maxRect(self, A):
		result = self.maxHist(A[0])
		for i in range(1, len(A)):
			for j in range(len(A[i])):
				if A[i][j]:
					A[i][j] += A[i - 1][j]
			result = max(result, self.maxHist(A[i]))
		return result

def main():
	t = int(input())
	r = Rect()
	while t > 0:
		(ROW, COL) = map(int, input().split())
		arr = []
		ones_count = 0
		for _ in range(ROW):
			f = list(map(int, list(input())))
			ones_count += sum(f)
			arr.append(f)
		res = r.maxRect(arr)
		print('YES' if res == ones_count else 'NO')
		t -= 1
main()


n = int(input())
for _ in range(n):
	flag = 0
	h = 1
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	for q in range(n):
		string = input()
		if string.find('1') >= 0:
			if flag == 0:
				flag = 1
				first = string
				continue
			if string != first:
				print('NO')
				for w in range(n - q - 1):
					input()
				h = 0
				break
	if h == 1:
		print('YES')


def solver(n, m, grid):
	(one, zero) = ('1', '0')
	for i in range(n):
		for j in range(m):
			if grid[i][j] == one:
				col = j
				while col < m and grid[i][col] == one:
					col += 1
				row = i
				while row < n and grid[row][j] == one:
					row += 1
				for ix in range(i, n):
					for jx in range(m):
						if i <= ix < row and j <= jx < col:
							if grid[ix][jx] == zero:
								return 'NO'
						elif grid[ix][jx] == one:
							return 'NO'
				return 'YES'
	return 'YES'
try:
	x = int(input())
	for _ in range(x):
		(n, m) = map(int, input().split())
		grid = []
		for i in range(n):
			grid.append(input())
		print(solver(n, m, grid))
except:
	pass


try:
	result = []
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = []
		flag = 0
		num = 0
		res = 'NO'
		for _ in range(n):
			a.append(list(input().strip()))
		for i in range(n):
			for j in range(m):
				if flag == 0 and a[i][j] == '1':
					start = [i, j]
					flag = 1
				if a[i][j] == '1':
					num += 1
					end = [i, j]
		for x in range(start[0], end[0] + 1):
			for y in range(start[1], end[1] + 1):
				if a[x][y] != '1':
					flag = 0
					break
		if (end[0] - start[0] + 1) * (end[1] - start[1] + 1) == num:
			res = 'YES'
		if flag == 0:
			res = 'NO'
		result.append(res)
	[print(a) for a in result]
except:
	pass


def solve(n, m, A):
	left = None
	right = None
	down = None
	up = None
	found = False
	for row in range(m):
		if found:
			break
		for col in range(n):
			if A[col][row] == '1':
				left = (col, row)
				found = True
				break
	found = False
	for row in range(m - 1, -1, -1):
		if found:
			break
		for col in range(n):
			if A[col][row] == '1':
				right = (col, row)
				found = True
				break
	found = False
	for row in range(n):
		if found:
			break
		for col in range(m):
			if A[row][col] == '1':
				up = (row, col)
				found = True
				break
	found = False
	for row in range(n - 1, -1, -1):
		if found:
			break
		for col in range(m):
			if A[row][col] == '1':
				down = (row, col)
				found = True
				break
	if right == None or left == None or up == None or (down == None):
		return 'NO'
	for row in range(up[0], down[0] + 1):
		for col in range(left[1], right[1] + 1):
			if A[row][col] == '0':
				return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	A = []
	for _ in range(n):
		s = input()
		A.append(list(s))
	print(solve(n, m, A))


t = int(input())
while t:
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(input())
	flag = True
	(starting, ending) = (None, None)
	for i in range(n):
		temp_start = mat[i].find('1')
		temp_last = mat[i].rfind('1')
		if temp_start >= 0 and mat[i][temp_start:temp_last + 1].find('0') >= 0:
			flag = False
			break
		elif temp_start >= 0 and starting == None and (ending == None):
			starting = temp_start
			ending = temp_last
			ind = i
		elif temp_start >= 0 and starting != None and (ending != None):
			if temp_last == ending and temp_start == starting:
				continue
			else:
				flag = False
				break
		if flag == False:
			break
	if flag and starting != None:
		print('YES')
	else:
		print('NO')
	t -= 1


def cal(matrix):
	n = len(matrix)
	m = len(matrix[0])
	for row in range(len(matrix)):
		for col in range(len(matrix[0])):
			if row - 1 > -1 and row + 1 < n:
				if matrix[row - 1][col] == '1' and matrix[row + 1][col] == '1' and (matrix[row][col] == '0'):
					return 'NO'
			if col - 1 > -1 and col + 1 < m:
				if matrix[row][col - 1] == '1' and matrix[row][col + 1] == '1' and (matrix[row][col] == '0'):
					return 'NO'
			if row - 1 > -1 and col - 1 > -1:
				if matrix[row][col - 1] == '1' and matrix[row - 1][col] == '1' and (matrix[row][col] == '0'):
					return 'NO'
			if row + 1 < n and col + 1 < m:
				if matrix[row + 1][col] == '1' and matrix[row][col + 1] == '1' and (matrix[row][col] == '0'):
					return 'NO'
			if row + 1 < n and col - 1 > -1:
				if matrix[row + 1][col] == '1' and matrix[row][col - 1] == '1' and (matrix[row][col] == '0'):
					return 'NO'
			if row - 1 > -1 and col + 1 < m:
				if matrix[row - 1][col] == '1' and matrix[row][col + 1] == '1' and (matrix[row][col] == '0'):
					return 'NO'
	return 'YES'
t = int(input())
ans = []
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	mat = []
	for i in range(n):
		mat.append(list(input()))
	ans.append(cal(mat))
for i in ans:
	print(i)


for _ in range(int(input())):
	arr = []
	(a, b) = list(map(int, input().split()))
	for i in range(a):
		brr = input()
		arr.append(brr)
	flag = 0
	for i in range(a):
		for j in range(b):
			if arr[i][j] == '1':
				fir = [i, j]
				flag = 1
				break
		if flag:
			break
	flag = 0
	for i in range(a - 1, -1, -1):
		for j in range(b - 1, -1, -1):
			if arr[i][j] == '1':
				las = [i, j]
				flag = 1
				break
		if flag:
			break
	flag = 0
	for i in range(a):
		for j in range(b):
			if arr[i][j] == '1':
				if i < fir[0] or i > las[0] or j < fir[1] or (j > las[1]):
					flag = 1
					break
			elif arr[i][j] == '0':
				if (i > fir[0] and i < las[0]) and (j > fir[1] and j < las[1]):
					flag = 1
					break
		if flag:
			break
	if flag:
		print('NO')
		continue
	print('YES')


for test in range(int(input())):
	(N, M) = map(int, input().split())
	a = [input() for i in range(N)]
	(ba, bb, ca, cb) = (float('inf'), float('-inf'), float('inf'), float('-inf'))
	for i in range(N):
		for j in range(M):
			if a[i][j] == '1':
				ba = min(ba, i)
				bb = max(ba, i)
				ca = min(ca, j)
				cb = max(cb, j)
	e = 0
	for i in range(ba, bb + 1):
		for j in range(ca, cb + 1):
			if a[i][j] == '0':
				e = 1
				break
	if e == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(list(str(input())))

	def solve():
		x_min = m
		x_max = -1
		y_min = n
		y_max = -1
		for i in range(n):
			for j in range(m):
				if mat[i][j] == '1':
					if x_min > j:
						x_min = j
					if x_max < j:
						x_max = j
					if y_min > i:
						y_min = i
					if y_max < i:
						y_max = i
		for i in range(y_min, y_max + 1):
			for j in range(x_min, x_max + 1):
				if mat[i][j] == '0':
					return 'NO'
		return 'YES'
	print(solve())


import re
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	grid = []
	for pp in range(N):
		grid.append(list(map(int, list(input()))))
	grid2 = []
	for i in range(N):
		if 1 in grid[i]:
			grid2.append(grid[i])
	temp = True
	for item in zip(*grid2):
		if item[0] == 0:
			if sum(item) == 0:
				continue
			else:
				print('NO')
				temp = False
				break
		if item[0] == 1:
			if sum(item) == len(item):
				continue
			else:
				print('NO')
				temp = False
				break
	if temp == True:
		print('YES')


try:
	t = int(input())
	for x in range(t):
		nm = input().split()
		n = int(nm[0])
		m = int(nm[1])
		arr = []
		brr = []
		count = 0
		for i in range(n):
			a = input()
			crr = []
			for j in range(m):
				if a[j] == '1':
					arr.append([i, j])
					count += 1
				crr.append(a[j])
			brr.append(crr)
		x = True
		if count > 0:
			for i in range(arr[0][0], arr[-1][0] + 1):
				for j in range(arr[0][1], arr[-1][1] + 1):
					if brr[i][j] == '0':
						x = False
						break
			pro = (arr[-1][0] + 1 - arr[0][0]) * (arr[-1][1] + 1 - arr[0][1])
			if x == True and count == pro:
				print('YES')
			else:
				print('NO')
		else:
			print('NO')
except:
	pass


T = int(input())
for _ in range(T):
	result = 'YES'
	index = 0
	(N, M) = list(map(int, input().split()))
	case = []
	index_mass = []
	for i in range(N):
		string = input()
		string = [int(simb) for simb in string]
		case.append(string)
	for i in case:
		flag = 0
		j = 0
		while j < len(i):
			if i[j] == 1:
				flag = 1
				index_mass.append(j)
			j += 1
		if flag == 1:
			index = case.index(i)
			break
	idx = 0
	while idx < len(index_mass) - 1:
		if index_mass[idx + 1] - index_mass[idx] != 1:
			result = 'NO'
		idx += 1
	while index < len(case):
		how = 0
		for k in case[index]:
			if k == 1 and (not case[index].index(k) in index_mass):
				result = 'NO'
			elif k == 1 and case[index].index(k) in index_mass:
				how += 1
		if how != len(index_mass) and 1 in case[index]:
			result = 'NO'
		index += 1
	if index_mass:
		print(result)
	else:
		print('NO')


try:
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		mat = []
		for _ in range(n):
			mat.append(list(input()))
		(lower_i, lower_j, upper_i, upper_j) = (n, m, -1, -1)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == '1':
					if i < lower_i:
						lower_i = i
					if j < lower_j:
						lower_j = j
					if upper_i < i:
						upper_i = i
					if upper_j < j:
						upper_j = j
		for x in range(lower_i, upper_i + 1):
			for y in range(lower_j, upper_j + 1):
				if mat[x][y] == '0':
					print('NO')
					break
			else:
				continue
			break
		else:
			print('YES')
except EOFError:
	pass


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	s = []
	for j in range(n):
		temp = input()
		s.append(temp)
	flag = 0
	flag1 = 0
	temp2 = '0' * m
	for j in range(n):
		if flag1 == 0:
			if s[j] == temp2:
				continue
		if flag == 0:
			if '1' in s[j] and flag1 == 0:
				temp = s[j]
				flag1 = 1
			elif flag1 == 1:
				if s[j] == temp:
					continue
				elif s[j] == temp2:
					continue
				else:
					print('NO')
					break
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	i = -1
	j = -1
	enter = False
	exit = False
	if '1' in s:
		i = s.index('1')
		j = n - s[::-1].index('1') - 1
		enter = True
	ss = s.strip('0')
	flag = True
	if '0' in ss:
		flag = False
	for kk in range(n - 1):
		s = input()
		if flag == True:
			ii = -1
			jj = -1
			if '1' in s:
				if enter == False:
					i = s.index('1')
					j = n - s[::-1].index('1') - 1
					enter = True
				if exit == True:
					flag = False
					continue
				ii = s.index('1')
				jj = n - s[::-1].index('1') - 1
				enter = True
			elif enter == True:
				exit = True
			if exit == True:
				continue
			ss = s.strip('0')
			if '0' in ss or ii != i or jj != j:
				flag = False
	if flag == False:
		print('NO')
	else:
		print('YES')


import re

def solve():
	num = str(input()).split(' ')
	n = int(num[0])
	m = int(num[1])
	s = []
	for i in range(n):
		s.append(str(input()))
	rec = []
	for i in s:
		temp = ''
		for j in range(len(i)):
			if i[j] == '1':
				temp += str(j)
		if temp != '':
			rec.append(temp)
	a = rec[0]
	flag = 1
	for i in rec:
		if a != i:
			flag = 0
	if flag:
		print('YES')
	else:
		print('NO')
testCase = int(input())
while testCase:
	solve()
	testCase -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(str, input().split())))
	r = []
	c = []
	for j in range(m):
		for i in range(n):
			c.append(a[i][0][j])
	for i in range(n):
		for j in range(m):
			r.append(a[i][0][j])
	R = []
	C = []
	for i in range(0, n * m, m):
		if '1' in r[i:m + i]:
			R.append(1)
		else:
			R.append(-1)
	for i in range(0, n * m, n):
		if '1' in c[i:i + n]:
			C.append(1)
		else:
			C.append(-1)
	lc = 0
	rc = 0
	lr = 0
	rr = 0
	for i in range(len(C)):
		if C[i] == 1:
			lc = i
			break
	for i in range(len(C) - 1, -1, -1):
		if C[i] == 1:
			rc = i
			break
	for i in range(len(R)):
		if R[i] == 1:
			lr = i
			break
	for i in range(len(R) - 1, -1, -1):
		if R[i] == 1:
			rr = i
			break
	f = 1
	for i in range(lr * m, (rr + 1) * m, m):
		if '0' in r[i + lc:rc + i + 1]:
			f = -1
	if f == -1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	l = []
	f = 1
	for j in range(m):
		s = input()
		if f == 1:
			t = []
			if len(l) == 0:
				for i in range(n):
					if s[i] == '1':
						l.append(i)
				for j in range(len(l) - 1):
					if l[j + 1] - l[j] != 1:
						f = 0
						break
			else:
				for i in range(n):
					if s[i] == '1':
						t.append(i)
				if len(t) > 0:
					if t != l:
						f = 0
	if f == 0:
		print('NO')
		continue
	print('YES')


test_case = int(input())
while test_case:
	(n, m) = map(int, input().split())
	ones = []
	not_possible = 0
	(f2, f4) = (0, 0)
	for i in range(n):
		row = input()
		indices = []
		count = 0
		(f1, f3) = (0, 0)
		for j in range(m):
			if row[j] == '1':
				indices.append(j)
				count += 1
				if f1 == 0:
					f1 = 1
				if f3 == 1 and f1 == 1:
					not_possible = 1
			elif f1 == 1:
				f3 = 1
		if indices:
			if f2 == 0:
				f2 = 1
			if f2 == 1 and f4 == 1:
				not_possible = 1
		elif f2 == 1:
			f4 = 1
		ones.append([i, count, indices])
	if not_possible == 1:
		print('NO')
	else:
		flag = 0
		for i in range(n - 1):
			if ones[i][2] and ones[i + 1][2]:
				if ones[i][2] != ones[i + 1][2]:
					flag = 1
					break
		if flag == 1:
			print('NO')
		else:
			print('YES')
	test_case -= 1


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
(tc,) = inp()
for _ in range(tc):
	(n, m) = inp()
	a = [[int(i) for i in input()] for j in range(n)]
	vis = [[False for i in range(m)] for j in range(n)]
	last = [-1] * m
	f = False
	final = True
	ones = sum([i.count(1) for i in a])
	start = -1
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				if f == False:
					start = i
				f = True
				last[j] = i
			elif f == True:
				break
		if f == True:
			break
	f = False
	for i in range(m):
		ind = last[i]
		while ind < n:
			if a[ind][i] == 1:
				f = True
				last[i] = ind
			else:
				break
			ind += 1
	if len(set(last)) > 2:
		final = False
	lol = list(sorted(set(last)))
	ans = last.count(lol[-1]) * (lol[-1] - start + 1)
	if ones != ans:
		final = False
	print('YES' if final else 'NO')