Given a square grid of characters in the range ascii[a-z], rearrange elements of each row alphabetically, ascending.  Determine if the columns are also in ascending alphabetical order, top to bottom.  Return YES if they are or NO if they are not.

Example 

$grid=[\text{'abc'},\text{'ade'},\text{'efg'}]$   

The grid is illustrated below.

a b c
a d e
e f g

The rows are already in alphabetical order.  The columns a a e, b d f and c e g are also in alphabetical order, so the answer would be YES.  Only elements within the same row can be rearranged.  They cannot be moved to a different row.

Function Description  

Complete the gridChallenge function in the editor below.  

gridChallenge has the following parameter(s):  

string grid[n]: an array of strings  

Returns   

string: either YES or NO  

Input Format

The first line contains $\boldsymbol{\boldsymbol{t}}$, the number of testcases.   

Each of the next $\boldsymbol{\boldsymbol{t}}$ sets of lines are described as follows: 

- The first line contains $n$, the number of rows and columns in the grid. 

- The next $n$ lines contains a string of length $n$

Constraints

$1\leq t\leq100$ 

$1\leq n\leq100$ 

Each string consists of lowercase letters in the range ascii[a-z]  

Output Format

For each test case, on a separate line print YES if it is possible to rearrange the grid alphabetically ascending in both its rows and columns, or NO otherwise.

Sample Input
STDIN   Function
-----   --------
1       t = 1
5       n = 5
ebacd   grid = ['ebacd', 'fghij', 'olmkn', 'trpqs', 'xywuv']
fghij
olmkn
trpqs
xywuv

Sample Output
YES

Explanation

The $5$x$5$ grid in the $\mbox{I}$ test case can be reordered to 

abcde
fghij
klmno
pqrst
uvwxy

This fulfills the condition since the rows 1, 2, ..., 5 and the columns 1, 2, ..., 5 are all alphabetically sorted.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def solve():
	n = int(input())
	a = [sorted(list(input())) for _ in range(n)]
	for i in range(n - 1):
		for j in range(n):
			if a[i][j] > a[i + 1][j]:
				print('NO')
				return
	print('YES')
t = int(input())
for _ in range(t):
	solve()


def can_ordered(b):
	n = len(b)
	m = len(b[0])
	for j in range(m):
		for i in range(n - 1):
			if b[i][j] > b[i + 1][j]:
				return False
	return True
for _ in range(int(input())):
	n = int(input())
	b = []
	for _ in range(n):
		b.append(sorted(input()))
	if can_ordered(b):
		print('YES')
	else:
		print('NO')


def sort_string(string):
	return ''.join(sorted(string))
for _ in range(int(input())):
	n = int(input())
	string = []
	for i in range(n):
		s = input()
		string.append(sort_string(s))
	value = True
	for j in range(n):
		for i in range(n - 1):
			if string[i][j] > string[i + 1][j]:
				value = False
				break
		if not value:
			break
	if value:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = [['' for j in range(n)] for k in range(n)]
	for j in range(n):
		temp = input()
		for k in range(n):
			l[j][k] = temp[k]
	flag = 1
	l[0].sort()
	j = 1
	while flag == 1 and j < n:
		l[j].sort()
		for k in range(n):
			if l[j][k] < l[j - 1][k]:
				flag = 0
				break
		j += 1
	if flag == 1:
		print('YES')
	else:
		print('NO')


def fun(M, n):
	for col in range(n):
		for row in range(n - 1):
			if not M[row][col] <= M[row + 1][col]:
				return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	M = []
	n = int(input())
	for i in range(n):
		myList = list(input())
		myList.sort()
		M.append(myList)
	print(fun(M, n))


def solve(G):
	N = len(G)
	for r in range(N):
		G[r] = sorted(G[r])
	for c in range(N):
		cs = list((G[r][c] for r in range(N)))
		if sorted(cs) != cs:
			return False
	return True
T = int(input())
for _ in range(T):
	N = int(input())
	G = [input() for _ in range(N)]
	print('YES' if solve(G) else 'NO')


def is_possible(grid, row):
	grid = [[y for y in x] for x in grid]
	for r in range(row):
		grid[r].sort()
	for c in range(row):
		for r in range(1, row):
			if grid[r][c] < grid[r - 1][c]:
				return 'NO'
	return 'YES'
tests = int(input())
for _ in range(tests):
	g = []
	rows = int(input())
	for _ in range(rows):
		g.append(input())
	print(is_possible(g, rows))


T = int(input())
for _ in range(T):
	N = int(input())
	G = []
	for i in range(N):
		G.append(list(input()))
		G[i].sort()
	valid = True
	for i in range(N):
		for j in range(1, N):
			if ord(G[j][i]) < ord(G[j - 1][i]):
				valid = False
				break
	if valid:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	found = 0
	N = int(input())
	data = [[i for i in input()] for j in range(N)]
	for i in range(N):
		data[i] = sorted(data[i])
	for i in range(N):
		column = [row[i] for row in data]
		if column != sorted(column):
			found = 1
			break
	if found:
		print('NO')
	else:
		print('YES')


def is_sorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))

def grid(a, n):
	possible = True
	for j in range(n):
		if not is_sorted([a[i][j] for i in range(n)]):
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		a.append(sorted([c for c in input()]))
	if grid(a, n):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	z = []
	for j in range(n):
		s = input()
		l = []
		for i in range(n):
			l.append(ord(s[i]))
		l.sort()
		z.append(l)
	k = 0
	for i in range(n - 1):
		for j in range(n):
			if z[i][j] > z[i + 1][j]:
				k += 1
				break
		if k > 0:
			break
	if k == 0:
		print('YES')
	else:
		print('NO')


def is_valid_grid(n, grid):
	for col in range(n):
		for row in range(n - 1):
			if grid[row][col] > grid[row + 1][col]:
				return 'NO'
	return 'YES'

def main():
	t = int(input())
	for x in range(t):
		n = int(input())
		grid = [1] * n
		for y in range(n):
			row = list(input())
			row.sort()
			grid[y] = row
		print(is_valid_grid(n, grid))
main()


for a in range(int(input())):
	ls1 = []
	ls2 = []
	res = 'YES'
	for b in range(int(input())):
		ls1 = ls2
		ls2 = sorted(list(input()))
		if len(ls1) > 0:
			for c in range(len(ls1)):
				if ls1[c] > ls2[c]:
					res = 'NO'
	print(res)


def lexSort(mat, sq):
	for i in range(sq):
		mat[i].sort()
	for i in range(sq - 1):
		for j in range(sq):
			if mat[i][j] > mat[i + 1][j]:
				return 'NO'
	return 'YES'
cases = int(input())
for c in range(cases):
	sq = int(input())
	mat = []
	for i in range(sq):
		mat.append(list(input().strip()))
	print(lexSort(mat, sq))


T = int(input())

def ascending(l):
	for n in range(1, len(l)):
		if l[n] < l[n - 1]:
			return False
	return True
for t in range(T):
	N = int(input())
	B = [[0] * N] * N
	for n in range(N):
		B[n] = [ord(_) for _ in input()]
		B[n].sort()
	C = list(map(list, zip(*B)))
	result = 'YES'
	for n in range(N):
		if not ascending(C[n]):
			result = 'NO'
			break
	print(result)


T = int(input())
for a in range(0, T):
	N = int(input())
	prev_row = None
	test = True
	for i in range(0, N):
		row = list(input())
		for j in range(0, N - 1):
			min_index = j + 1
			for k in range(j + 1, N):
				if row[k] < row[min_index]:
					min_index = k
			if row[min_index] < row[j]:
				t = row[j]
				row[j] = row[min_index]
				row[min_index] = t
		if prev_row != None:
			for j in range(0, N):
				if prev_row[j] > row[j]:
					test = False
		prev_row = row
	print('YES' if test else 'NO')


def order(matrix):
	ret_val = []
	for row in matrix:
		ret_val.append(sorted(row))
	return ret_val

def is_list_ordered(l):
	prev = l[0]
	for item in l[1:]:
		if item < prev:
			return False
		prev = item

def is_it_ordered(matrix):
	for row in matrix:
		if is_list_ordered(row) is False:
			return False
	for column_index in range(len(matrix[0])):
		column = [row[column_index] for row in matrix]
		if is_list_ordered(column) is False:
			return False
	return True
T = int(input())
for t in range(T):
	N = int(input())
	matrix = []
	for n in range(N):
		row = list(input())
		matrix.append(row)
	matrix = order(matrix)
	ordered = is_it_ordered(matrix)
	print('YES') if ordered is True else print('NO')


from sys import stdin

def lexord(string_list):
	sorted_row = [''.join(sorted(x)) for x in string_list]
	columns = ['' for x in sorted_row[0]]
	for y in range(len(sorted_row[0])):
		columns[y] = ''.join((sorted_row[x][y] for x in range(len(sorted_row))))
	sorted_column = True
	for x in columns:
		sorted_column = sorted_column and ''.join(sorted(x)) == x
		if not sorted_column:
			break
	return sorted_column
T = int(stdin.readline())
for x in range(T):
	N = int(stdin.readline())
	string_list = [stdin.readline().rstrip('\n') for y in range(N)]
	if lexord(string_list):
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	N = int(input())
	Grid = [list(input()) for _ in range(N)]
	for row in Grid:
		row.sort()
	flag = 0
	for col in range(N):
		for row in range(1, N):
			if Grid[row - 1][col] > Grid[row][col]:
				print('NO')
				flag = 1
				break
		if flag:
			break
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	grid = [''] * n
	flag = 0
	for i in range(n):
		grid[i] = input()
		grid[i] = ''.join(sorted(grid[i]))
	for i in range(n):
		s = ''
		for j in range(n):
			s += grid[j][i]
		if s != ''.join(sorted(s)):
			flag = 1
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	N = int(input())
	s = []
	for __ in range(N):
		ss = str(input()).strip()
		s.append(sorted(ss))
	good = 'YES'
	for i in range(N - 1):
		for j in range(N):
			if s[i][j] > s[i + 1][j]:
				good = 'NO'
				break
	print(good)


def get():
	return int(input())

def getl():
	return input()

def sortable(arr, size):
	for i in range(0, size):
		for j in range(0, size - 1):
			if arr[j][i] > arr[j + 1][i]:
				return False
	return True
cases = get()
for i in range(0, cases):
	size = get()
	arr = []
	for j in range(0, size):
		arr.append(''.join(sorted(getl())))
	if sortable(arr, size):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [sorted(input()) for i in range(n)]
	flag = True
	for i in range(n):
		for j in range(0, n - 1):
			if arr[j][i] > arr[j + 1][i]:
				flag = False
				break
		if not flag:
			break
	if flag:
		print('YES')
	else:
		print('NO')


def ans(g, n):
	for i in range(n):
		for j in range(n - 1):
			if ord(g[j + 1][i]) - ord(g[j][i]) < 0:
				return 'NO'
	return 'YES'
T = int(input())
for t in range(T):
	n = int(input())
	g = []
	for i in range(n):
		g.append(list(input()))
	for c in g:
		c.sort()
	print(ans(g, n))


def mergeSort(alist):
	if len(alist) > 1:
		mid = len(alist) // 2
		lefthalf = alist[:mid]
		righthalf = alist[mid:]
		mergeSort(lefthalf)
		mergeSort(righthalf)
		i = 0
		j = 0
		k = 0
		while i < len(lefthalf) and j < len(righthalf):
			if lefthalf[i] < righthalf[j]:
				alist[k] = lefthalf[i]
				i = i + 1
			else:
				alist[k] = righthalf[j]
				j = j + 1
			k = k + 1
		while i < len(lefthalf):
			alist[k] = lefthalf[i]
			i = i + 1
			k = k + 1
		while j < len(righthalf):
			alist[k] = righthalf[j]
			j = j + 1
			k = k + 1

def findmax(A):
	length = len(A)
	max = A[0]
	for i in range(1, length):
		if max < A[i]:
			max = A[i]
	return max
T = int(input())
for _ in range(T):
	N = int(input())
	G = []
	for i in range(N):
		G.append(list(input()))
	flag = 1
	for i in range(N):
		mergeSort(G[i])
		if i > 0:
			for j in range(N):
				if G[i - 1][j] > G[i][j]:
					flag = 0
					break
	if flag == 1:
		print('YES')
	else:
		print('NO')


numTestCases = int(input())
while numTestCases > 0:
	numTestCases -= 1
	flag = False
	m = 0
	n = 0
	mat = []
	m = int(input())
	n = m
	for i in range(m):
		line = list(input())
		line.sort()
		mat.append(line)
	for i in range(m):
		for j in range(m - 1):
			if mat[j][i] > mat[j + 1][i]:
				flag = True
	if flag == False:
		print('YES')
	else:
		print('NO')


def f(grid):
	for row in grid:
		row.sort()
	for column in range(len(grid)):
		for row in range(0, len(grid) - 1):
			if grid[row][column] > grid[row + 1][column]:
				return False
	return True
numTests = int(input())
for i in range(numTests):
	size = int(input())
	matrix = []
	for row in range(size):
		matrix.append(list(input()))
	result = f(matrix)
	if result:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	N = int(input())
	grid = [sorted(input()) for _ in range(N)]

	def is_sorted():
		for r in range(1, N):
			for c in range(N):
				if grid[r][c] < grid[r - 1][c]:
					return False
		return True
	print('YES' if is_sorted() else 'NO')


t = int(input())
for i in range(t):
	n = int(input())
	grid = [['a' for x in range(n)] for x in range(n)]
	for i in range(0, n):
		s = str(input())
		j = 0
		for y in range(1, n + 1):
			if y == 1:
				grid[i][j] = s[:y]
			else:
				grid[i][j] = s[y - 1:y]
			j += 1
		grid[i] = sorted(grid[i])
	col_sorted_grid = [['a' for x in range(n)] for x in range(n)]
	is_sorted = 'YES'
	for i in range(0, n):
		l = []
		for j in range(i, i + 1):
			for k in range(0, n):
				l.append(grid[k][j])
		if l == sorted(l):
			continue
		else:
			is_sorted = 'NO'
			break
	print(is_sorted)


cases = int(input())
for i in range(cases):
	dim = int(input())
	grid = []
	result = 'YES'
	for i in range(dim):
		grid.append([x for x in input()])
	for i in range(len(grid)):
		grid[i].sort()
	for i in range(len(grid)):
		if result == 'NO':
			break
		for j in range(len(grid) - 1):
			if grid[i][j] > grid[i][j + 1]:
				result = 'NO'
				break
	for i in range(len(grid)):
		if result == 'NO':
			break
		for j in range(len(grid) - 1):
			if grid[j][i] > grid[j + 1][i]:
				result = 'NO'
				break
	print(result)


def check_columns(N, grid):
	for j in range(N):
		for i in range(1, N):
			if grid[i][j] < grid[i - 1][j]:
				return False
	return True
T = int(input())
for _ in range(T):
	N = int(input())
	grid = [input() for _ in range(N)]
	for i in range(N):
		grid[i] = sorted(grid[i])
	if check_columns(N, grid):
		print('YES')
	else:
		print('NO')


import fileinput

def checkIfSolvable(A):
	N = len(A)
	for i in range(N):
		for j in range(N):
			A[i].sort()
	for j in range(N):
		col = [A[i][j] for i in range(N)]
		if not all((col[i] <= col[i + 1] for i in range(len(col) - 1))):
			return 'NO'
	return 'YES'
lines = [l.strip('\n') for l in fileinput.input()]
T = int(lines[0])
ind = 1
for i in range(T):
	N = int(lines[ind])
	ind += 1
	A = [list(l) for l in lines[ind:ind + N]]
	ind += N
	print(checkIfSolvable(A))


def check_grid(n):
	grid = []
	for i in range(n):
		line = input()
		grid.append(list(line))
		grid[i].sort()
		if i > 0:
			for j in range(n):
				if grid[i - 1][j] > grid[i][j]:
					error = True
					for k in range(n - i - 1):
						input()
					return True
	return False
t = int(input())
for ii in range(0, t):
	n = int(input())
	if check_grid(n):
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	g = [sorted(input()) for i in range(n)]
	print('YES' if all((g[i][j] <= g[i + 1][j] for i in range(n - 1) for j in range(n))) else 'NO')


t = int(input())
for itr in range(t):
	n = int(input())
	a = list()
	invalid = 0
	for i in range(n):
		a.append([_ for _ in input()])
		a[i].sort()
	for i in range(1, n):
		for j in range(n):
			if a[i][j] < a[i - 1][j]:
				invalid = 1
				break
		if invalid:
			break
	if invalid:
		print('NO')
	else:
		print('YES')


T = int(input())
for i in range(T):
	N = int(input())
	sorted_rows = []
	for j in range(N):
		sorted_rows.append(sorted(input()))
	result = 'YES'
	for j in range(N):
		for pair in zip(range(0, N), range(1, N)):
			if sorted_rows[pair[0]][j] > sorted_rows[pair[1]][j]:
				result = 'NO'
	print(result)


a = int(input())
while a > 0:
	a -= 1
	b = int(input())
	flag = 0
	Matrix = [[0 for x in range(b)] for x in range(b)]
	for i in range(b):
		d = input()
		m = list(d)
		m.sort()
		Matrix[i] = m
	for i in range(b - 1):
		for j in range(b):
			if Matrix[i][j] > Matrix[i + 1][j]:
				flag = 1
				break
	if flag == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for tc in range(t):
	n = int(input())
	grid = []
	for ni in range(n):
		grid.append(input())
	for o in range(n - 1):
		count = 0
		for (i, j) in zip(sorted(grid[o]), sorted(grid[o + 1])):
			if i <= j:
				count = count + 1
		if count != n:
			print('NO')
			break
	else:
		print('YES')


for t in range(int(input())):
	N = int(input())
	m = []
	for i in range(N):
		m.append(list(sorted(input())))
	ok = True
	for i in range(1, N):
		for j in range(N):
			if m[i - 1][j] > m[i][j]:
				ok = False
				break
	if ok:
		print('YES')
	else:
		print('NO')


w = int(input())
sa = 0
while sa != w:
	x = int(input())
	i = 0
	k = ''
	s = []
	while i != x:
		t = []
		k = input('')
		for l in k:
			t.append(l)
		t.sort()
		s.append(t)
		i += 1
	i = 0
	r = 0
	while i != x - 1:
		if r == 1:
			break
		for k in range(x):
			if s[i][k] > s[i + 1][k]:
				r = 1
		i += 1
	if r == 1:
		print('NO')
	elif r == 0:
		print('YES')
	sa = sa + 1


def listify(s):
	L = []
	for i in s:
		L.append(i)
	L.sort()
	return L

def grid_sorted(L):
	for i in range(len(L)):
		for j in range(len(L) - 1):
			if L[j][i] > L[j + 1][i]:
				return 'NO'
	return 'YES'
numTrials = int(input())
for i in range(numTrials):
	L = []
	num = int(input())
	for i in range(num):
		row = input()
		L.append(listify(row))
	print(grid_sorted(L))


t = int(input())
for x in range(0, t):
	n = int(input())
	words = []
	res = 'YES'
	for i in range(0, n):
		words.append(''.join(sorted(input())))
		if i > 0:
			for j in range(0, len(words[i])):
				if words[i - 1][j] > words[i][j]:
					res = 'NO'
	print(res)


t = int(input())
while t > 0:
	f = []
	z = input()
	n = int(z)
	for x in range(n):
		s = input()
		l = list(s)
		l.sort()
		f.append(l)
	if n == 1:
		print('YES')
	else:
		flag = 0
		for i in range(n):
			for j in range(n - 1):
				if f[j][i] > f[j + 1][i]:
					flag = 1
					break
			if flag == 1:
				break
		if flag == 1:
			print('NO')
		else:
			print('YES')
	t -= 1


T = int(input())
for t in range(T):
	N = int(input())
	G = []
	for x in range(N):
		G.append(sorted(list(input())))
	sortable = True
	for i in range(N - 1):
		for j in range(N):
			if G[i][j] > G[i + 1][j]:
				sortable = False
				break
	print('YES' if sortable else 'NO')


T = int(input())
for i in range(T):
	N = int(input())
	r0 = sorted(input())
	flag = 'YES'
	for j in range(1, N):
		rj = sorted(input())
		for k in range(N):
			if r0[k] > rj[k]:
				flag = 'NO'
		r0 = rj
	print(flag)


tstCs = int(input())
ans = []
for _ in range(0, tstCs):
	theGrid = []
	grid = int(input())
	for _ in range(0, grid):
		row = sorted(list(input()))
		theGrid.append(row)
		row = []
	if grid == 1:
		ans.append('YES')
		continue
	m = True
	while m == True:
		for i in range(0, len(theGrid)):
			if m == False:
				break
			for j in range(0, len(theGrid) - 1):
				if theGrid[j][i] <= theGrid[j + 1][i]:
					if i == len(theGrid) - 1 and j == len(theGrid) - 2:
						ans.append('YES')
						m = False
				else:
					ans.append('NO')
					m = False
					break
for itm in ans:
	print(itm)


T = int(input())
for _ in range(T):
	N = int(input())
	grid = []
	for i in range(N):
		grid.append(sorted(input()))
	possible = all((grid[i][j] <= grid[i + 1][j] for i in range(N - 1) for j in range(N)))
	print('YES') if possible else print('NO')


def check_rows(grid):
	for i in range(len(grid)):
		column = []
		for j in range(len(grid)):
			column.append(grid[j][i])
		if sorted(column) != column:
			print('NO')
			return
	print('YES')
for _ in range(int(input())):
	grid = []
	for _ in range(int(input())):
		grid.append(sorted(input()))
	check_rows(grid)


def isSorted(L):
	if len(L) == 1:
		return True
	return L[0] <= L[1] and isSorted(L[1:])
t = int(input())
while t:
	result = 'YES'
	n = int(input())
	l = n
	L = []
	while l:
		L.append(input())
		l -= 1
	for i in range(n):
		L[i] = ''.join(sorted(L[i]))
	LT = []
	for i in range(n):
		temL = []
		for j in range(n):
			temL.append(L[j][i])
		LT.append(temL)
	for i in range(n):
		if not isSorted(LT[i]):
			result = 'NO'
	print(result)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	data = []
	for j in range(N):
		data.append(sorted(input()))
	check_lex = True
	for j in range(0, N):
		for k in range(1, N):
			if data[k][j] < data[k - 1][j]:
				check_lex = False
	if check_lex:
		print('YES')
	else:
		print('NO')


cases = int(input())
for _ in range(cases):
	n = int(input())
	grid = []
	for _ in range(n):
		row = list(input())
		row.sort()
		grid.append(row)
	transposed_grid = []
	for c in range(n):
		column = []
		for r in range(n):
			column.append(grid[r][c])
		transposed_grid.append(column)
	print('YES' if all((sorted(column) == column for column in transposed_grid)) else 'NO')


def solve(N, G):
	for r in G:
		r.sort()
	for i in range(N):
		for j in range(N - 1):
			if G[j][i] > G[j + 1][i]:
				return 'NO'
	return 'YES'
T = int(input())
for t in range(T):
	N = int(input())
	G = []
	for n in range(N):
		G.append([c for c in input()])
	print(solve(N, G))


testcases = int(input())
for test in range(testcases):
	numLines = int(input())
	if numLines == 1:
		input()
		print('YES')
	else:
		curr = sorted(input())
		sol_possible = True
		for _ in range(1, numLines):
			next = sorted(input())
			if sol_possible == True:
				for index in range(numLines):
					if curr[index] > next[index]:
						sol_possible = False
						break
			curr = next
		if sol_possible == False:
			print('NO')
			sol_possible = True
		else:
			print('YES')


def process():
	n = int(input())
	ina = []
	res = 'YES'
	for i in range(n):
		s = str(input())
		ia = [c for c in s]
		ia.sort()
		ina.append(ia)
	for j in range(n):
		for i in range(1, n):
			if ina[i][j] < ina[i - 1][j]:
				res = 'NO'
				return res
	return res
t = int(input())
for ti in range(t):
	print(process())


T = int(input())

def bubblesort(row):
	length = len(row)
	notdoneyet = True
	while notdoneyet:
		notdoneyet = False
		for i in range(length - 1):
			if islexi(row[i], row[i + 1]):
				notdoneyet = True
				temp_letter = row[i + 1]
				row[i + 1] = row[i]
				row[i] = temp_letter
	return row

def islexi(a, b):
	if ord(a) > ord(b):
		return True
	else:
		return False
for t in range(T):
	N = int(input())
	mat = []
	for j in range(N):
		mat.append([])
		for letter in list(input()):
			mat[j].append(letter)
	ispossible = 'YES'
	for i in range(N):
		mat[i][:] = bubblesort(mat[i][:])
		if i > 0:
			for j in range(N):
				if islexi(mat[i - 1][j], mat[i][j]):
					ispossible = 'NO'
					break
	print(ispossible)


def main():
	t = int(input())
	for _ in range(t):
		g = []
		n = int(input())
		for _ in range(n):
			g.append(sorted(input()))
		is_sorted = True
		for i in range(n):
			c = [g[j][i] for j in range(n)]
			if c != sorted(c):
				is_sorted = False
				break
		print('YES' if is_sorted else 'NO')
main()


def can_be_sorted(m):
	for line in m:
		line.sort()
	for (i, line) in enumerate(m):
		for j in range(1, len(line)):
			if m[j - 1][i] > m[j][i]:
				return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	m = [list(input()) for _ in range(n)]
	print('YES' if can_be_sorted(m) else 'NO')


t = int(input())
for _ in range(t):
	l = []
	possible = True
	n = int(input())
	for _ in range(n):
		row = input()
		l.append(sorted(row))
	for j in range(n):
		for i in range(n - 1):
			if l[i][j] > l[i + 1][j]:
				possible = False
				break
		if not possible:
			break
	if possible:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	solvable = True
	grid = ['' for h in range(N)]
	for j in range(N):
		grid[j] = sorted(input())
		for h in range(N):
			if j > 0 and grid[j - 1][h] > grid[j][h]:
				solvable = False
	if solvable:
		print('YES')
	else:
		print('NO')


t = int(input())
for x in range(t):
	n = int(input())
	data = []
	for i in range(n):
		line = input()
		line = [c for c in line]
		data.append(sorted(line))
	flag = 0
	for i in range(0, n):
		for j in range(0, n - 1):
			if data[j][i] > data[j + 1][i]:
				flag = 1
				break
		if flag == 1:
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')


def solve():
	n = int(input())
	a = [sorted(list(input())) for _ in range(n)]
	for i in range(n - 1):
		for j in range(n):
			if a[i][j] > a[i + 1][j]:
				print('NO')
				return
	print('YES')
t = int(input())
for _ in range(t):
	solve()


n = int(input())
for a in range(n):
	i = int(input())
	grid = []
	for b in range(i):
		grid.append(sorted(input()))
	for l in zip(*grid):
		if not all((l[i] <= l[i + 1] for i in range(len(l) - 1))):
			print('NO')
			break
	else:
		print('YES')


T = int(input())
for Ti in range(T):
	N = int(input())
	m = [sorted([v for v in input()]) for Ni in range(N)]
	answer = 'YES'
	for y in range(N):
		for x in range(N):
			if x + 1 < N and m[y][x] > m[y][x + 1] or (y + 1 < N and m[y][x] > m[y + 1][x]):
				answer = 'NO'
				break
		if answer == 'NO':
			break
	print(answer)


for i in range(int(input())):
	n = int(input())
	g = []
	for i in range(n):
		g.append(list(input()))
	for i in range(n):
		g[i].sort()
	yes = True
	for i in range(1, n):
		for j in range(n):
			if g[i][j] < g[i - 1][j]:
				yes = False
	if yes:
		print('YES')
	else:
		print('NO')


def doit(G, N):
	for i in range(1, N):
		for j in range(N):
			if G[i][j] < G[i - 1][j]:
				print('NO')
				return
	print('YES')
T = int(input())
for _ in range(T):
	N = int(input())
	G = [list(input()) for x in range(N)]
	for x in G:
		x.sort()
	doit(G, N)


def sortRow(s):
	l = sorted(list(s))
	return ''.join(l)
T = int(input())
for i in range(T):
	N = int(input())
	values = []
	for i in range(N):
		s = sortRow(input())
		values.append(s)
	alpha = True
	for column in range(N):
		for row in range(1, N):
			if values[row - 1][column] > values[row][column]:
				alpha = False
	if alpha:
		print('YES')
	else:
		print('NO')


import string
from collections import OrderedDict
dick = OrderedDict(zip(string.ascii_lowercase, range(26)))

def findPossible(ls, n):
	freq = [0 for j in range(26)]
	for j in ls[0]:
		freq[dick[j]] += 1
	for j in range(1, 26):
		freq[j] += freq[j - 1]
	for j in range(1, n):
		temp_freq = [0 for i in range(26)]
		for k in ls[j]:
			temp_freq[dick[k]] += 1
		for k in range(26):
			if k != 0:
				temp_freq[k] += temp_freq[k - 1]
			if temp_freq[k] > freq[k]:
				return False
		freq = temp_freq
	return True
t = int(input())
for i in range(t):
	n = int(input())
	ls = []
	for j in range(n):
		ls.append(input())
	if findPossible(ls, n):
		print('YES')
	else:
		print('NO')


def checkCols(arr):
	for i in range(len(arr)):
		for j in range(len(arr) - 1):
			if arr[j][i] > arr[j + 1][i]:
				return 'NO'
	return 'YES'
T = int(input())
for t in range(T):
	N = int(input())
	arr = []
	for n in range(N):
		arr.append(input())
	arr = [sorted(el) for el in arr]
	print(checkCols(arr))


t = int(input())
c = 0
while c < t:
	c += 1
	n = int(input())
	cn = 0
	g = []
	good = True
	while cn < n:
		cn += 1
		g.append([x for x in input()])
		g[-1].sort()
	for idx in range(len(g) - 1):
		for jdx in range(len(g[idx]) - 1):
			if g[idx][jdx + 1] < g[idx][jdx] or g[idx + 1][jdx] < g[idx][jdx]:
				good = False
				break
		if not good:
			break
	if good:
		for jdx in range(len(g[-1]) - 1):
			if g[-1][jdx + 1] < g[-1][jdx] or g[jdx + 1][-1] < g[jdx][-1]:
				good = False
				break
	if good:
		print('YES')
	else:
		print('NO')


def is_ordered(matrix, N):
	for i in range(1, N):
		for j in range(N):
			if matrix[i][j] < matrix[i - 1][j]:
				return False
	return True
T = int(input())
for _ in range(T):
	matrix = []
	N = int(input())
	for i in range(N):
		local = list(input())
		local.sort()
		matrix.append(local)
	if is_ordered(matrix, N):
		print('YES')
	else:
		print('NO')


import fileinput
input = fileinput.input()
T = int(input.readline())
for t in range(T):
	N = int(input.readline())
	lines = []
	success = True
	for n in range(N):
		lines += [sorted(input.readline().strip())]
	for j in range(N):
		col = []
		for i in range(1, N):
			if lines[i][j] < lines[i - 1][j]:
				success = False
	if success:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = []
	for i in range(n):
		a.append(' '.join(input()).split())
		a[i].sort()
	f = 1
	for i in range(n):
		if f == 0:
			break
		for j in range(n - 1):
			if a[j][i] > a[j + 1][i]:
				f = 0
				break
	if f:
		print('YES')
	else:
		print('NO')


t = int(input())
if 1 <= t <= 100:
	for i in range(t):
		n = int(input())
		if 1 <= n <= 100:
			b = []
			for j in range(n):
				a = []
				s = input()
				for k in range(n):
					a.append(s[k])
				b.append(sorted(a))
			l = 0
			for j in range(n):
				for k in range(n - 1):
					if b[j][k] > b[j][k + 1]:
						l = 1
						break
			for j in range(n - 1):
				for k in range(n):
					if b[j][k] > b[j + 1][k]:
						l = 1
						break
			if l == 1:
				print('NO')
			else:
				print('YES')


t = int(input())
for i in range(t):
	a = []
	n = int(input())
	for i in range(n):
		a.append([])
		s = input()
		for j in range(n):
			a[i].append(s[j])
		a[i].sort()
	flag = 0
	for j in range(n):
		for i in range(n - 1):
			if a[i][j] > a[i + 1][j]:
				flag = 1
				print('NO')
				break
		if flag == 1:
			break
	if flag == 0:
		print('YES')


def GridChallenge(Array):
	for a in Array:
		a.sort()
	for i in range(0, N):
		for j in range(0, N - 1):
			if Array[j][i] > Array[j + 1][i]:
				return 'NO'
	return 'YES'
T = int(input())
for _ in range(0, T):
	N = int(input())
	L = []
	for i in range(0, N):
		L.append(list(input()))
	print(GridChallenge(L))


def testcase():
	grid = {}
	N = int(input())
	for n in range(0, N):
		grid[n] = sorted(input())
	for n in range(0, N):
		for m in range(0, N - 1):
			if grid[m][n] > grid[m + 1][n]:
				return 'NO'
	return 'YES'
T = int(input())
for t in range(0, T):
	print(testcase())


T = int(input())
for j in range(T):
	N = int(input())
	str_arr = []
	for i in range(N):
		str_arr.append(sorted(input()))
	flag = True
	for i in range(N):
		for k in range(N - 1):
			if str_arr[k][i] > str_arr[k + 1][i]:
				flag = False
				break
	if flag:
		print('YES')
	else:
		print('NO')


__author__ = 'nolanemirot'

def gridChallenge(arr):
	tmp = 'a'
	for e in arr:
		if tmp <= e:
			tmp = e
		else:
			return False
	return True

def checkColumn(arr, wl):
	x = 0
	while x < wl:
		y = 0
		tmp = 'a'
		while y < wl:
			elemen = arr[y][x]
			if tmp <= elemen:
				tmp = elemen
			else:
				return False
			y += 1
		x += 1
	return True
nb_test_case = int(input())
for i in range(nb_test_case):
	size = int(input())
	l = ''
	c = []
	for e in range(size):
		line = input()
		a = gridChallenge(sorted(line))
		b = sorted(line)
		c.append(b)
		if a == 'NO':
			print(a)
			break
	if checkColumn(c, size):
		print('YES')
	else:
		print('NO')


def doShit(rows, N):
	for x in range(N):
		for y in range(N - 1):
			if rows[y][x] > rows[y + 1][x]:
				print('NO')
				return
	print('YES')
	return
for _ in range(int(input())):
	rows = []
	N = int(input())
	for _ in range(N):
		rows.append(sorted(input()))
	doShit(rows, N)


t = int(input())
for _ in range(t):
	n = int(input())
	M = []
	for _ in range(n):
		M.append(sorted(list(input())))
	ok = True
	for j in range(n):
		if not all((M[i][j] <= M[i + 1][j] for i in range(n - 1))):
			ok = False
			break
	if ok:
		print('YES')
	else:
		print('NO')


def grid(arr):
	for col in list(zip(*arr)):
		if list(col) != sorted(col):
			return 'NO'
	return 'YES'
T = int(input())
for t in range(T):
	N = int(input())
	arr = []
	for n in range(N):
		arr.append(sorted(input()))
	print(grid(arr))


def grid_is_sorted(grid):
	for i in range(len(grid)):
		column = []
		for n in range(len(grid)):
			column.append(grid[n][i])
		if column != sorted(column):
			return False
	return True
num_tests = int(input())
for test_num in range(num_tests):
	grid_size = int(input())
	sorted_grid = []
	for _ in range(grid_size):
		row = input()
		sorted_grid.append(sorted((c for c in row)))
	output = 'YES' if grid_is_sorted(sorted_grid) else 'NO'
	print(output)


t = eval(input())
while t > 0:
	t -= 1
	n = eval(input())
	flag = True
	s = 'a' * n
	freq = [0] * 26
	freq[0] = n
	for k in range(n):
		prevS = s
		s = input()
		if flag:
			prevFreq = freq
			freq = [0] * 26
			for i in range(n):
				freq[ord(s[i]) - ord('a')] += 1
			s = ''
			for i in range(26):
				s += chr(ord('a') + i) * freq[i]
			for i in range(n):
				if prevS[i] > s[i]:
					flag = False
	print('YES' if flag else 'NO')


tests = int(input())
for _ in range(tests):
	N = int(input())
	rows = [sorted(input()) for _ in range(N)]
	if all((list(x) == sorted(x) for x in zip(*rows))):
		print('YES')
	else:
		print('NO')


def is_grid_lexicographic(grid):
	sorted_grid = [sorted(x) for x in grid]
	for i in range(len(grid)):
		column = [x[i] for x in sorted_grid]
		if sorted(column) != column:
			return False
	return True
for i in range(int(input())):
	size = int(input())
	grid = []
	while size > 0:
		grid.append(input())
		size -= 1
	print('YES' if is_grid_lexicographic(grid) else 'NO')


tests = int(input())
for test in range(tests):
	size = int(input())
	matrix = [['a' for r in range(size)] for c in range(size)]
	for r in range(size):
		matrix[r] = list(input())
	for r in range(size):
		change = True
		counter = size - 1
		while counter > 0 and change:
			change = False
			for c in range(counter):
				if ord(matrix[r][c]) > ord(matrix[r][c + 1]):
					change = True
					(matrix[r][c], matrix[r][c + 1]) = (matrix[r][c + 1], matrix[r][c])
			counter -= 1
	ordered = True
	for r in range(size - 1):
		for c in range(size):
			if ord(matrix[r][c]) > ord(matrix[r + 1][c]):
				ordered = False
				break
	if ordered == True:
		print('YES')
	else:
		print('NO')
	test += 1


T = int(input())
for _ in range(T):
	N = int(input())
	g = []
	for _ in range(N):
		g.append(sorted(input()))
	possible = True
	for index in range(N):
		col = [row[index] for row in g]
		if sorted(col) != col:
			possible = False
			break
	if possible:
		print('YES')
	else:
		print('NO')


import fileinput as f
lines = [i for i in f.input()]
times = int(lines[0])
line_no = 1
for i in range(times):
	size = int(lines[line_no])
	line_no += 1
	grid = []
	broken = False
	for j in range(size):
		grid.append(''.join(sorted(lines[line_no].strip())))
		line_no += 1
	for j in range(size):
		if not sorted([k[j] for k in grid]) == [k[j] for k in grid]:
			print('NO')
			broken = True
			break
	if not broken:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for _ in range(n):
		a += [sorted(input())]
	if all((a[j][i] <= a[j + 1][i] for i in range(n) for j in range(n - 1))):
		print('YES')
	else:
		print('NO')


class Matrix(object):

	def __init__(self, arr):
		self.mat = arr
		self.rows = len(arr)
		self.cols = len(arr[0])
		lens = [len(row) for row in arr]
		if min(lens) != max(lens):
			raise ValueError('A matrix must have rows of equal length.')

	def __str__(self):
		return '\n'.join((str(row) for row in self.mat))

	def column(self, ind):
		if 0 > ind or ind >= self.cols:
			raise ValueError('Colun index out of range.')
		col = []
		for row in range(self.rows):
			col.append(self.mat[row][ind])
		return col

	def is_col_sorted(self):
		for col in range(self.cols):
			if not is_sorted(self.column(col)):
				return False
		return True

	def is_row_sorted(self):
		return all((is_sorted(row) for row in self.mat))

	def sort_by_rows(self):
		for row in self.mat:
			row.sort()

def is_sorted(arr):
	if len(arr):
		elm = arr[0]
		for mem in arr:
			if mem < elm:
				return False
			elm = mem
	return True
numtests = int(input(''))
for _ in range(numtests):
	grid = []
	rows = int(input(''))
	for _ in range(rows):
		grid.append(list(input('')))
	mat = Matrix(grid)
	mat.sort_by_rows()
	if mat.is_row_sorted() and mat.is_col_sorted():
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	G = []
	N = int(input())
	for n in range(N):
		a = list(input())
		a.sort()
		G.append(a)
	H = []
	for n in range(N):
		a = [l[n] for l in G]
		a.sort()
		H.append(a)
	ok = True
	for x in range(N):
		for y in range(N):
			if G[x][y] != H[y][x]:
				ok = False
	if ok:
		print('YES')
	else:
		print('NO')


def sort_char_list(char_list):
	return sorted(char_list)

def check_row_lexicographic_order(char_grid, row_num):
	curr_char = char_grid[row_num][0]
	for char in char_grid[row_num][1:]:
		if curr_char > char:
			return False
		current_char = char
	return True

def check_col_lexicographic_order(char_grid, col_num):
	curr_char = char_grid[0][col_num]
	row_num = 1
	while row_num < len(char_grid):
		if curr_char > char_grid[row_num][col_num]:
			return False
		curr_char = char_grid[row_num][col_num]
		row_num += 1
	return True

def check_lexicographic_sort(num_elts, char_grid):
	for i in range(num_elts):
		char_grid[i] = sort_char_list(char_grid[i])
	for i in range(num_elts):
		if not check_col_lexicographic_order(char_grid, i):
			return False
	return True

def main():
	num_cases = int(input().strip())
	for i in range(num_cases):
		num_elts = int(input().strip())
		char_grid = []
		for i in range(num_elts):
			char = input().strip()
			char_grid.append([char[i] for i in range(len(char))])
		if check_lexicographic_sort(num_elts, char_grid):
			print('YES')
		else:
			print('NO')
main()


def grid_challenge(N, G):
	for i in range(N):
		for j in range(N):
			k = j
			while k > 0 and G[i][k - 1] > G[i][k]:
				(G[i][k], G[i][k - 1]) = (G[i][k - 1], G[i][k])
				k -= 1
	for i in range(N):
		for j in range(1, N):
			if G[j - 1][i] > G[j][i]:
				return 'NO'
	return 'YES'

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		G = []
		for _ in range(N):
			G.append([ord(c) for c in input()])
		print(grid_challenge(N, G))
main()


T = int(input())
for t in range(0, T):
	N = int(input())
	arr = []
	for i in range(0, N):
		arr.append([])
		temp = input()
		for j in range(0, N):
			arr[i].append(temp[j])
		arr[i].sort()
	result = 'YES'
	for i in range(0, N):
		for j in range(0, N - 1):
			if arr[j][i] > arr[j + 1][i]:
				result = 'NO'
				break
		if result == 'NO':
			break
	print(result)


def check(list1, dim):
	for j in range(0, dim):
		a = 0
		for i in list1:
			if a > ord(i[j]):
				return 'NO'
			a = ord(i[j])
	return 'YES'
T = int(input())
for i in range(0, T):
	list1 = []
	s = int(input())
	for j in range(0, s):
		string = input()
		mylist = []
		for k in string:
			mylist.append(k)
		mylist.sort()
		list1.append(mylist)
	print(check(list1, s))


__author__ = 'chamathsilva'
for _ in range(int(input())):
	N = int(input())
	grid = [list(input()) for i in range(N)]
	index = 1
	grid[0].sort()
	while index < N:
		grid[index].sort()
		for i in range(N):
			if grid[index - 1][i] > grid[index][i]:
				index = float('inf')
				break
		index += 1
	print(['NO', 'YES'][index == N])


def checkLex(arr, n):
	for j in range(n - 1):
		for k in range(n):
			if arr[j][k] > arr[j + 1][k]:
				return False
	return True
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	line = []
	for j in range(n):
		x = list(input().strip())
		x.sort()
		line.append(x)
	if checkLex(line, n):
		print('YES')
	else:
		print('NO')


T = int(input())
for t in range(T):
	N = int(input())
	l = []
	for n in range(N):
		l.append(sorted(list(input())))
	for i in range(N):
		for j in range(N - 1):
			if l[j][i] > l[j + 1][i]:
				break
		else:
			continue
		print('NO')
		break
	else:
		print('YES')


def solve(n):
	g = [''.join(sorted(input())) for _ in range(n)]
	for row in g:
		for j in range(n - 1):
			if row[j] > row[j + 1]:
				return 'NO'
	g = zip(*g)
	g = [''.join(x) for x in g]
	for row in g:
		for j in range(n - 1):
			if row[j] > row[j + 1]:
				return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(solve(int(input())))