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

Chef is studying computer science. Tomorrow, he has an exam on algorithms and data structures. One of the algorithms he is required to study is the Hungarian algorithm (you do not have to know this algorithm to solve this problem).

In the Hungarian algorithm, you start with a matrix of positive integers with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$). The algorithm proceeds in steps.

In the first step, for each row of the matrix, you should find the smallest element in this row (let's denote it by $A$) and subtract $A$ from each element of the matrix in this row.

In the second step, for each column of the matrix, you should find the smallest element in this column (let's denote it by $A$) and subtract $A$ from each element in this column. The remaining steps of the algorithm are not relevant in this problem.

Currently, Chef is practicing implementation of the first two steps of the algorithm. He wants you to check if he is doing these two steps correctly or not. You are given a matrix with $N$ rows and $N$ columns; let's denote the element of this matrix in the $i$-th row and $j$-th column by $a_{i, j}$. Determine if this matrix can be the result of applying the first two steps of the Hungarian algorithm on some matrix.

------  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 a single integer $N$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of the following $N$ lines contains $N$ space-separated integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, N}$.

------  Output ------
For each test case, print a single line containing the string "YES" (without quotes) if the given matrix can be a result of the first two steps or "NO" (without quotes) if it cannot.

------  Constraints  ------
$1 ≤ T ≤ 10,000$
$2 ≤ N ≤ 500$
$0 ≤ a_{i, j} ≤ 10^{3}$ for each valid $i, j$
the sum of $N^{2}$ over all test cases does not exceed $2 \cdot 10^{6}$

----- Sample Input 1 ------ 
5
3
0 0 4
3 0 1
0 1 0
2
0 5
3 2
2
1 3
5 0
3
0 3 4
4 0 5
6 5 0
4
3 0 2 4
0 2 3 5
3 4 3 0
3 4 0 3
----- Sample Output 1 ------ 
YES
NO
NO
YES
YES
----- explanation 1 ------ 
Example case 1: Let's consider the matrix

3 1 5
7 2 3
5 4 3

and apply the first two steps of the Hungarian algorithm on it.

In the first step:
- the smallest integer in row $1$ is $1$
- the smallest integer in row $2$ is $2$
- the smallest integer in row $3$ is $3$

After subtracting, the matrix becomes

2 0 4
5 0 1
2 1 0

and the second step is performed on this matrix. In the second step:
- the smallest integer in column $1$ is $2$
- the smallest integer in column $2$ is $0$
- the smallest integer in column $3$ is $0$

After subtracting, the resulting matrix is

0 0 4
3 0 1
0 1 0

and this is the matrix given on the input, so the answer is YES.

Example case 2: It is impossible to find a matrix such that after applying the first two steps of the Hungarian algorithm, it becomes the matrix given on the input, so the answer is NO.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	col = set()
	row = []
	flag = 1
	for i in range(n):
		row.append(list(map(int, input().split())))
	for i in range(n):
		if flag:
			flag = 0
			for j in range(n):
				if row[i][j] == 0:
					col.add(j + 1)
					flag = 1
		else:
			break
	print('YES' if flag and sum(list(col)) == n * (n + 1) // 2 else 'NO')


for _ in range(int(input())):
	n = int(input())
	rows = []
	for i in range(n):
		rows.append([int(x) for x in input().split()])
	columns = []
	for i in range(n):
		col = []
		for j in range(n):
			col.append(rows[j][i])
		columns.append(col)
	p = True
	for i in rows:
		if 0 not in i:
			p = False
			break
	for i in columns:
		if 0 not in i:
			p = False
			break
	print('YES' if p else 'NO')


for tc in range(int(input())):
	poss = True
	n = int(input())
	rows = []
	cols = []
	for i in range(n):
		rows.append(list(map(int, input().split())))
	for j in range(n):
		col = [rows[i][j] for i in range(n)]
		cols.append(col)
	for row in rows:
		if 0 not in row:
			poss = False
	for col in cols:
		if 0 not in col:
			poss = False
	print('YES' if poss else 'NO')


for _ in range(int(input())):
	n = int(input())
	arr = []
	column = []
	for i in range(n):
		arr.append([int(m) for m in input().split()])
	for k in range(n):
		column.append([arr[j][k] for j in range(n)])
	flag = 1
	for a in arr:
		if 0 not in a:
			flag = 0
			break
		else:
			continue
	if flag == 1:
		for c in column:
			if 0 not in c:
				flag = 0
			else:
				continue
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	llst = []
	flagr = 1
	cc = []
	for i in range(n):
		lst = list(map(int, input().split()))
		if flagr:
			if 0 not in lst:
				flagr = 0
		llst.append(lst)
		if len(cc) == 0:
			for j in lst:
				cc.append([j])
		else:
			for j in range(n):
				cc[j].append(lst[j])
	flagc = 1
	for i in cc:
		if 0 not in i:
			flagc = 0
			break
	if flagr and flagc:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	l = []
	flag = 0
	for x in range(n):
		a = list(map(int, input().split()))
		l.append(a)
		for i in l[x]:
			if i == 0:
				flag += 1
				break
	s = []
	for x in range(n):
		for y in range(n):
			if l[x][y] == 0:
				s.append(y)
	if len(set(s)) == n and flag == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	lst = []
	for _ in range(int(input())):
		lst.append(list(map(int, input().split(' '))))
	lst1 = []
	for ele in lst:
		a = min(ele)
		lst1.append([i - a for i in ele])
	for i in range(len(lst1)):
		m = 10 ** 3
		for ele in lst1:
			if ele[i] < m:
				m = ele[i]
		for ele in lst1:
			ele[i] = ele[i] - m
	if lst == lst1:
		print('YES')
	else:
		print('NO')


t = input()
for c in range(0, int(t)):
	n = int(input())
	mat = []
	z = 0
	for i in range(n):
		a = list(map(int, input().split()))
		mat.append(a)
		if 0 not in mat[i]:
			z = 1
	f = 0
	if z == 0:
		for j in range(n):
			f = 0
			for i in range(n):
				if mat[i][j] == 0:
					f = 1
					break
			if f == 0:
				break
	if f == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	flag = 1
	matrix = []
	for _ in range(n):
		matrix.append(list(map(int, input().split())))
	for row in matrix:
		if 0 not in row:
			print('NO')
			flag = 0
			break
	if flag == 0:
		continue
	trans = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			trans[i][j] = matrix[j][i]
	for row in trans:
		if 0 not in row:
			print('NO')
			flag = 0
			break
	if flag == 1:
		print('YES')


for _ in range(int(input())):
	flag = 0
	n = int(input())
	mat = []
	for i in range(n):
		a = list(map(int, input().split()))
		mat.append(a)
		for i in mat[i]:
			if i == 0:
				flag += 1
				break
	b = []
	for i in range(n):
		for j in range(n):
			if mat[i][j] == 0:
				b.append(j)
	if len(set(b)) == n and flag == n:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	N = int(input())
	lst = []
	for j in range(N):
		k = input()
		kk = k.split()
		small = []
		for m in range(N):
			small.append(int(kk[m]))
		lst.append(small.copy())
	valid = True
	for n in range(N):
		count = 0
		for t in range(N):
			if lst[n][t] == 0:
				count += 1
		if count == 0:
			valid = False
			break
	for n in range(N):
		count = 0
		for t in range(N):
			if lst[t][n] == 0:
				count += 1
		if count == 0:
			valid = False
			break
	if valid == True:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	c = 0
	c1 = 0
	for i in range(n):
		a.append(list(map(int, input().split())))
	for i in range(n):
		if min(a[i]) == 0:
			c += 1
	for i in range(n):
		b = []
		for j in range(n):
			b.append(a[j][i])
		if min(b) == 0:
			c1 += 1
	if c == n and c1 == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	(cntRow, cntCol) = (set(), set())
	mat = []
	for _ in range(n):
		mat.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			if not mat[i][j]:
				cntRow.add(i)
				cntCol.add(j)
	if cntRow == cntCol and len(cntRow) == n:
		print('YES')
	else:
		print('NO')


T = int(input())
for x in range(T):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	row = set()
	col = set()
	for i in range(len(a)):
		for j in range(len(a)):
			if a[i][j] == 0:
				row.add(i)
				col.add(j)
	if len(row) == n and len(col) == n:
		print('YES')
	else:
		print('NO')


def column(matrix, p):
	return [row[p] for row in matrix]
t = int(input())
for i in range(t):
	n = int(input())
	entries = []
	flag = True
	for j in range(n):
		entries.append(list(map(int, input().split())))
	for row in entries:
		if 0 in row:
			continue
		else:
			flag = False
			break
	for k in range(n):
		if 0 in column(entries, k):
			continue
		else:
			flag = False
			break
	if flag is False:
		print('NO')
	else:
		print('YES')


def solve(matrix, num):
	rw = set()
	cl = set()
	for i in range(num):
		for j in range(num):
			if matrix[i][j] == 0:
				rw.add(i)
				cl.add(j)
	if len(rw) == num and len(cl) == num:
		return 'YES'
	else:
		return 'NO'
for i in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		rw = list(map(int, input().split()))
		a.append(rw)
	print(solve(a, n))


def checkHungarian(m, n):
	column = []
	row = []
	for i in range(n):
		for j in range(n):
			if m[i][j] == 0:
				if i not in row:
					row.append(i)
				if j not in column:
					column.append(j)
	if len(column) == n and len(row) == n:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	n = int(input())
	ls = [1] * n
	for i in range(n):
		a = list(map(int, input().split()))[:n]
		ls[i] = a
	checkHungarian(ls, n)


def solve(num, matrix):
	col = []
	row = []
	ans = None
	for i in range(num):
		for j in range(num):
			if matrix[i][j] == 0:
				if i not in col:
					col.append(i)
				if j not in row:
					row.append(j)
	if len(col) == num and len(row) == num:
		ans = 'YES'
	else:
		ans = 'NO'
	return ans
for _ in range(int(input())):
	n = int(input())
	matrix = []
	for _ in range(n):
		columns = list(map(int, input().split()))
		matrix.append(columns)
	print(solve(n, matrix))


for _ in range(int(input())):
	n = int(input())
	a = []
	for k in range(n):
		row = list(map(int, input().split()))
		a.append(row)
	col = []
	row = []
	for i in range(n):
		for j in range(n):
			if a[i][j] == 0:
				if i not in col:
					col.append(i)
				if j not in row:
					row.append(j)
	if len(col) == n and len(row) == n:
		print('YES')
	else:
		print('NO')


from collections import Counter, UserString
mod = lambda n: n % (10 ** 9 + 7)
fc_ = [1]
for i in range(1, 1000001):
	fc_.append(i * fc_[i - 1])
	fc_[i] = mod(fc_[i])

def fact(n):
	return fc_[n]

def printm(n):
	print(mod(n))

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r1 = lambda n: range(n)
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	n = ii()
	l = []
	a = set()
	b = set()
	for i in r1(n):
		m = li()
		l.append(m)
		c = 0
		for (ind, j) in enumerate(m):
			if j == 0:
				a.add(i)
				b.add(ind)
	if len(a) == n and len(b) == n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	r = set()
	c = set()
	for i in range(n):
		l1 = list(map(int, input().split()))
		for j in range(len(l1)):
			if l1[j] == 0:
				r.add(i)
				c.add(j)
	if len(r) == n and len(c) == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = []
	(q, r) = ([], [])
	l = 0
	for i in range(n):
		s = list(map(int, input().split()))
		arr.append(s)
	for i in range(n):
		m = 1
		x = list(arr[i])
		for i in range(n):
			if x[i] == 0:
				q.append(i)
				m = m * 0
		l = l + m
	for i in range(n):
		r.append(i)
	q = list(set(q))
	q.sort()
	if q == r and l == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	n = int(input())
	ans = []
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for j in range(1, n + 1):
			x = l[j - 1]
			if x == 0:
				if ans.count(i) == 0:
					ans.append(i)
				if ans.count(-1 * j) == 0:
					ans.append(-1 * j)
	if len(ans) == 2 * n:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	p = []
	q = []
	r = []
	l = 0
	for i in range(n):
		a = list(map(int, input().split()))
		p.append(a)
	for i in range(n):
		m = 1
		x = list(p[i])
		for i in range(n):
			if x[i] == 0:
				q.append(i)
				m = m * 0
		l = l + m
	for i in range(n):
		r.append(i)
	q = list(set(q))
	q.sort()
	if q == r and l == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = []
	row = []
	col = []
	for i in range(n):
		list2 = list(map(int, input().split()))
		list1.append(list2)
		for j in range(n):
			if list1[i][j] == 0:
				row.append(i)
				col.append(j)
	if len(set(row)) == n and len(set(col)) == n:
		print('YES')
	else:
		print('NO')


import numpy as np
t = int(input())
for i in range(t):
	n = int(input())
	mat = [list(map(int, input().split())) for i in range(n)]
	a = True
	c = []
	for i in range(n):
		b = []
		for j in range(n):
			b.append(mat[j][i])
		c.append(b)
	for i in range(n):
		if 0 not in mat[i]:
			a = False
			break
	for i in range(n):
		if 0 not in c[i]:
			a = False
	if a:
		print('YES')
	else:
		print('NO')


def hung(a, n):
	for i in range(n):
		if 0 not in a[i]:
			return 'NO'
	for i in range(n):
		mn = a[0][i]
		for j in range(n):
			mn = min(mn, a[j][i])
		if mn != 0:
			return 'NO'
	return 'YES'
for i in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		s = list(map(int, input().split()))
		a.append(s)
	print(hung(a, n))


tests = int(input())
for i in range(tests):
	n = int(input())
	ans = 'YES'
	arr = []
	for j in range(n):
		sub_arr = list(map(int, input().split()))
		arr.append(sub_arr)
		minimum = min(sub_arr)
		if minimum:
			ans = 'NO'
	col = 0
	while ans == 'YES' and col < n:
		minimum = arr[0][col]
		for j in range(n):
			minimum = min(minimum, arr[j][col])
		if minimum:
			ans = 'NO'
		col += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	matrix = [[] for i in range(n)]
	flag = True
	for i in range(n):
		li = list(map(int, input().split(' ')))
		a = 0
		for j in li:
			matrix[a].append(j)
			a += 1
		if 0 not in li:
			flag = False
	if flag == False:
		print('NO')
	else:
		for i in matrix:
			if 0 not in i:
				flag = False
		if flag:
			print('YES')
		else:
			print('NO')


def tranpose(a, n):
	b = []
	for i in range(n):
		r = []
		for j in range(n):
			r.append(a[j][i])
		b.append(r)
	for i in range(n):
		if 0 not in a[i]:
			return False
	for i in range(n):
		if 0 not in b[i]:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		r = list(map(int, input().split()))
		a.append(r)
	if tranpose(a, n):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	list2 = [[] for x in range(n)]
	okay = 1
	for j in range(n):
		list1 = list(map(int, input().split()))
		z = 0
		for s in list1:
			list2[z].append(s)
			z += 1
		if 0 not in list1:
			okay = 0
	if okay == 0:
		print('NO')
	else:
		for y in list2:
			if 0 not in y:
				okay = 0
		if okay == 0:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	l1 = []
	for i in range(n):
		l1.append([int(x) for x in input().split(' ')])
	flag = 1
	for i in range(n):
		for j in range(n):
			if l1[i][j] == 0:
				break
			if j == n - 1 and l1[i][j] != 0:
				flag = 0
		if flag == 0:
			break
	if flag == 1:
		for i in range(n):
			for j in range(n):
				if l1[j][i] == 0:
					break
				if j == n - 1 and l1[j][i] != 0:
					flag = 0
			if flag == 0:
				break
	if flag == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	count = 0
	col = [[arr[j][i] for j in range(n)] for i in range(n)]
	for i in range(n):
		if 0 in arr[i] and 0 in col[i]:
			count += 1
	if n == count:
		print('YES')
	else:
		print('NO')


import numpy as np
import math as m
t = int(input())
for _ in range(t):
	x = int(input())
	arr = []
	for i in range(x):
		lis = list(map(int, input().split(' ')))
		arr.append(lis)
	arr = np.array(arr)
	bool = True
	for i in arr:
		if 0 not in i:
			bool = False
			break
	arr = np.transpose(arr)
	for i in arr:
		if 0 not in i:
			bool = False
			break
	if bool == True:
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	a = [0] * n
	for i in range(n):
		a[i] = [int(_) for _ in input().split()]
	row = [10000] * n
	col = [10000] * n
	for i in range(n):
		for j in range(n):
			row[i] = min(row[i], a[i][j])
			col[j] = min(col[j], a[i][j])
	for i in range(n):
		if row[i] != 0 or col[i] != 0:
			return 'NO'
	return 'YES'
t = int(input())
while t:
	t -= 1
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	zero = 'YES'
	count = []
	for j in range(n):
		s = [int(x) for x in input().split()]
		c = s.count(0)
		if c == 0:
			zero = 'NO'
		for i in range(c):
			count.append(s.index(0) + i)
			s.remove(0)
	if zero == 'NO':
		print('NO')
	elif len(set(count)) == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	b = []
	for i in range(n):
		b.append([0] * n)
	for i in range(n):
		for j in range(n):
			b[j][i] = a[i][j]
	t = True
	for i in a:
		if min(i) == 0:
			pass
		else:
			t = False
			break
	for i in b:
		if min(i) == 0:
			pass
		else:
			t = False
			break
	if t:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	A = []
	invalidated = False
	for _ in range(N):
		if invalidated:
			input()
			continue
		T = [int(s) for s in input().split()]
		if 0 not in T:
			invalidated = True
			continue
		A.append(T)
	if not invalidated:
		for i in range(N):
			if all((A[j][i] for j in range(N))):
				invalidated = True
				break
	print('NO' if invalidated else 'YES')


n = int(input())
while n > 0:
	x = int(input())
	a = []
	for i in range(0, x):
		w = input()
		w = w.split(' ')
		a.append(w)
	z = 0
	y = 0
	u = 0
	v = 0
	for i in range(0, x):
		for j in range(0, x):
			if a[i][j] == '0':
				z = z + 1
				break
	for i in range(0, x):
		for j in range(0, x):
			if a[j][i] == '0':
				u = u + 1
				break
	if z + u == 2 * x:
		print('YES')
	else:
		print('NO')
	n = n - 1


for _ in range(int(input())):
	n = int(input())
	mat = []
	for ___ in range(n):
		temp = list(map(int, input().split()))
		mat.append(temp)
	ans = True
	for i in range(n):
		(row, col) = (False, False)
		if not ans:
			break
		for j in range(n):
			if mat[i][j] == 0:
				row = True
			if mat[j][i] == 0:
				col = True
		if not (row and col):
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(0, T):
	a = int(input())
	mt = []
	for j in range(0, a):
		b = input().split()
		mt.append(b)
	doit = True
	for j in range(0, a):
		for k in range(0, a):
			if mt[j][k] == '0':
				break
		else:
			doit = False
			break
	if doit:
		for j in range(0, a):
			for k in range(0, a):
				if mt[k][j] == '0':
					break
			else:
				doit = False
				break
	if doit:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	row = []
	c = 0
	n = int(input())
	for i in range(n):
		row.append(list(map(int, input().split())))
	col = [[row[k][j] for k in range(n)] for j in range(n)]
	for i in range(n):
		if 0 in row[i] and 0 in col[i]:
			c += 1
	if c == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	matrix = list()
	flag = 0
	for i in range(n):
		li = list(map(int, input().split()))
		if 0 not in li:
			flag = -1
		res = [i for (i, value) in enumerate(li) if i not in matrix and value == 0]
		if len(res) > 0:
			matrix.extend(res)
	if len(matrix) == n and flag == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	b = []
	cnt = 0
	a = int(input())
	for i in range(a):
		c = list(map(int, input().split()))
		b.append(c)
	d = [[b[k][j] for k in range(a)] for j in range(a)]
	for i in range(a):
		if 0 in b[i] and 0 in d[i]:
			cnt += 1
		else:
			cnt = 0
	if cnt == a:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	(rows, cols) = ([0] * n, [0] * n)
	for r in range(n):
		arr = list(map(int, input().split(' ')))
		for (index, item) in enumerate(arr):
			if item == 0:
				rows[r] = 1
				cols[index] = 1
	if 0 not in rows and 0 not in cols:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = []
	invalid = 0
	for i in range(n):
		a = list(map(int, input().split()))
		l.append(a)
		if 0 not in a:
			invalid = 1
	for row in range(n):
		val = 0
		for col in range(n):
			if l[col][row] == 0:
				val = 1
		if val == 0:
			invalid = 1
			break
	if invalid == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for j in range(t):
	n = int(input())
	c = []
	d = 0
	for k in range(n):
		a = list(map(int, input().split()))
		c.append(a)
		if 0 not in a:
			d = 1
	for l in range(n):
		v = 0
		for m in range(n):
			if c[m][l] == 0:
				v = 1
		if v == 0:
			d = 1
			break
	if d == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n_rows = int(input())
	matrix = list()
	for j in range(n_rows):
		row = list(map(int, input().split(' ')))
		matrix.append(row)
	count = 0
	for j in range(n_rows):
		(flag1, flag2) = (1, 1)
		for k in range(n_rows):
			flag1 *= matrix[j][k]
			flag2 *= matrix[k][j]
		if flag1 == 0 and flag2 == 0:
			count += 1
	if count == n_rows:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = []
	for i in range(0, n):
		b = [int(x) for x in input().split()]
		a.append(b)
	flag = 0
	col = 0
	for i in range(0, n):
		prod = 1
		for j in range(0, n):
			prod = prod * a[i][j]
		if prod != 0:
			flag = 1
			break
	for j in range(0, n):
		prod_col = 1
		for i in range(0, n):
			prod_col = prod_col * a[i][j]
		if prod_col != 0:
			col += 1
			break
	if flag == 0 and col == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	t = int(input())
	c = 0
	grid = []
	for i in range(t):
		l = list(map(int, input().split()))
		grid.append(l)
		if 0 not in l:
			c = 1
	for i in range(t):
		v = 0
		for j in range(t):
			if grid[j][i] == 0:
				v = 1
				break
		if v == 0:
			c = 1
			break
	if c == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	matrix = [0 for i in range(n)]
	count = [0 for i in range(n)]
	for i in range(n):
		row = list(map(int, input().split()))
		for (j, e) in enumerate(row):
			if e == 0:
				matrix[j] = 1
				count[i] = 1
	print('YES' if sum(matrix) == sum(count) == n else 'NO')


def check_column(m, temp):
	f = True
	for i in range(temp):
		k = False
		for j in range(temp):
			if m[j][i] == 0:
				k = True
		if not k:
			f = False
			break
	return f
for _ in range(int(input())):
	n = int(input())
	m = []
	flag = True
	for i in range(n):
		a = list(map(int, input().split()))
		if 0 not in a:
			flag = False
		m.append(a)
	if not flag:
		print('NO')
	elif check_column(m, n):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

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

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

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())
success = 'YES'
failure = 'NO'

def solve(*args):
	(n, matx) = args
	cols = [1] * n
	for l in matx:
		try:
			ll = l.index(0)
			cols = [min(x, y) for (x, y) in zip(cols, l)]
		except ValueError:
			return failure
	return success if max(cols) == 0 else failure

def do_codechef():
	for t in rii():
		n = ii()
		matx = list()
		for _ in range(n):
			a = lmii()
			matx.append(a)
		print(solve(n, matx))
do_codechef()
exit()