Due to the COVID pandemic, there has been an increase in the number of cases if a hospital. The management has decided to clear a large square area for the patients and arrange for beds. But the beds can't be too near to each other.
The area is of dimension $N$ x $N$
The whole area is already divided into blocks. $1$ means there's a bed in the block, $0$ denotes there isn't. Note, beds placed on consecutive diagonal blocks are safe.
This is a SAFE example:
1 0
0 1
This is an UNSAFE example:
0 1 1
0 0 0
1 0 0
To avoid spreading the virus even further, you have to make sure no two adjacent blocks have beds in them. This is done to maintain distance between beds.
Return an output of "SAFE" if you find the workers have arranged the beds with due consideration to the distance needed. Return "UNSAFE" otherwise.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Next line contains $N$.
- Next $N$ lines will contain $N$ number of space-separated integers $Ai$ which make denote the beds in the area.

-----Output:-----
For each test case, output in a single line whether the total arrangement is "SAFE" or "UNSAFE". Even if there's a single unsafe bed in the whole area, report the whole area as "UNSAFE".

-----Constraints-----
- $1 \leq T \leq 100$
- $0 \leq Ai \leq 1$
- $2 \leq N \leq 100$

-----Subtasks-----
- 30 points : $1 \leq N \leq 7$
- 70 points : Original constraints

-----Sample Input:-----
2
4
1 0 1 0
0 0 0 1
0 1 0 0
1 0 0 1
4
1 0 1 0
0 0 0 0
1 0 1 1
0 1 0 0

-----Sample Output:-----
SAFE
UNSAFE

-----EXPLANATION:-----
Beds placed on blocks diagonally are not a problem.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
res = []
for _ in range(int(input())):
	lst = []
	flag = 0
	n = int(input())
	for i in range(n):
		lst.append(list(map(int, input().split())))
	for i in lst:
		for j in range(n - 1):
			if i[j] == i[j + 1] == 1:
				res.append('UNSAFE')
				flag = 1
				break
		if flag != 0:
			break
	for i in range(n - 1):
		for j in range(n):
			if lst[i][j] == lst[i + 1] == 1:
				res.append('UNSAFE')
				flag = 1
				break
		if flag != 0:
			break
	if flag == 0:
		res.append('SAFE')
for i in res:
	print(i)


T = int(input())
for t in range(T):
	N = int(input())
	l = []
	for i in range(N):
		l.append(list(map(int, input().split())))
	flg = True
	for i in range(N):
		for j in range(1, N):
			if l[i][j] == l[i][j - 1] and l[i][j] == 1:
				flg = False
				break
		if flg == False:
			break
	if flg == False:
		print('UNSAFE')
	else:
		for i in range(1, N):
			for j in range(N):
				if l[i][j] == l[i - 1][j] and l[i][j] == 1:
					flg = False
					break
			if flg == False:
				break
		if flg == False:
			print('UNSAFE')
		else:
			print('SAFE')


for _ in range(int(input())):
	n = int(input())
	l = []
	f = 0
	while not l or len(l) < len(l[0]):
		l.append(list(map(int, input().split())))
	a = sum(l, [])
	b = [i for i in range(len(a)) if a[i] == 1]
	for j in range(len(b) - 1):
		if b[j + 1] - b[j] == 1:
			f = 1
			print('UNSAFE')
			break
	if f != 1:
		print('SAFE')


t = int(input())
for i in range(t):
	b = int(input())
	g = []
	for i in range(b):
		s = []
		l = list(map(int, input().split()))
		for i in range(len(l)):
			if l[i] == 1:
				s.append(i)
		if len(s) == 1:
			g.append('SAFE')
		else:
			for i in range(len(s) - 1):
				if s[i + 1] - s[i] >= 2:
					g.append('SAFE')
				else:
					g.append('UNSAFE')
	if 'UNSAFE' in g:
		print('UNSAFE')
	else:
		print('SAFE')


for _ in range(int(input())):
	n = int(input())
	ar = [[0] * n] * n
	for i in range(n):
		ar[i] = list(map(int, input().split()))
	flag = 1
	for r in range(n - 1):
		for c in range(n - 1):
			if ar[r][c] == 1:
				if ar[r][c + 1] == 1:
					flag = 0
					break
				elif ar[r + 1][c] == 1:
					flag = 0
					break
	if flag == 1:
		print('SAFE')
	else:
		print('UNSAFE')


try:
	t = int(input())
	for i in range(t):
		rc = int(input())
		matr = []
		flag = 0
		for i in range(rc):
			matr.append(list(map(int, input().split())))
		for i in range(rc - 1):
			for j in range(rc - 1):
				if matr[i][j] == 1:
					if matr[i + 1][j] == 1 or matr[i][j + 1] == 1:
						flag = 1
						break
				if flag == 1:
					break
		if flag == 1:
			print('UNSAFE')
		else:
			print('SAFE')
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	cnt = 0
	arr = [[0 for j in range(n)] for i in range(n)]
	for i in range(n):
		l = list(map(int, input().split()))
		arr.insert(i, l)
		arr.pop()
	for i in range(n - 1):
		for j in range(n - 1):
			if arr[i][j] == arr[i][j + 1]:
				if arr[i][j + 1] == 1:
					cnt = 1
					break
			elif arr[i][j] == arr[i + 1][j]:
				if arr[i + 1][j] == 1:
					cnt = 1
					break
	if cnt == 0:
		print('SAFE')
	else:
		print('UNSAFE')


for ts in range(int(input())):
	N = int(input())
	l = []
	f = 1
	while not l or len(l) < len(l[0]):
		l.append(list(map(int, input().split())))
	p = sum(l, [])
	k = [i for i in range(len(p)) if p[i] == 1]
	for j in range(len(k) - 1):
		if k[j + 1] - k[j] == 1:
			f = 0
			break
	if f == 0:
		print('UNSAFE')
	else:
		print('SAFE')


try:
	for i in range(int(input())):
		n = int(input())
		li = []
		for j in range(n):
			li.append(list(map(int, input().split())))
		x = 0
		for k in range(n):
			for j in range(n):
				if k != n - 1 and j != n - 1:
					if li[k][j] == 1:
						if li[k][j + 1] == 1 or li[k + 1][j] == 1:
							x = 1
							break
				elif j == n - 1 and k != n - 1:
					if li[k][j] == 1:
						if li[k + 1][j] == 1:
							x = 1
							break
				elif k == n - 1 and j != n - 1:
					if li[k][j] == 1:
						if li[k][j + 1] == 1:
							x = 1
							break
			if x == 1:
				print('UNSAFE')
				break
		if x == 0:
			print('SAFE')
except:
	pass


t = int(input())
for xx in range(t):
	n = int(input())
	A = []
	for i in range(n):
		A.append([int(x) for x in input().split()])
	check = 0
	for i in range(n):
		for j in range(n):
			if A[i][j] == 1:
				if i < n - 1 and A[i + 1][j] == 1:
					check = 1
					break
				elif j < n - 1 and A[i][j + 1] == 1:
					check = 1
					break
		if check == 1:
			break
	if check == 0:
		print('SAFE')
	else:
		print('UNSAFE')


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	flag = 1
	for i in range(n - 1):
		for j in range(n - 1):
			if a[i][j] == 1:
				if a[i + 1][j] == 1 or a[i][j + 1] == 1:
					flag = 0
					break
				else:
					pass
	j = 0
	i = n - 1
	while j < n - 1:
		if a[i][j] == 1:
			if a[i][j + 1] == 1:
				flag = 0
				break
			else:
				pass
		j += 1
	i = 0
	j = n - 1
	while i < n - 1:
		if a[i][j] == 1:
			if a[i + 1][j] == 1:
				flag = 0
				break
			else:
				pass
		i += 1
	if flag == 1:
		print('SAFE')
	else:
		print('UNSAFE')


T = int(input())
for t in range(T):
	N = int(input())
	mat = []
	for i in range(N):
		mat.append(list(map(int, input().strip().split())))
	safe = True
	for i in range(N - 1):
		for j in range(N - 1):
			if mat[i][j] == 1:
				if mat[i + 1][j] == 1:
					safe = False
					break
				if mat[i][j + 1] == 1:
					safe = False
					break
		if not safe:
			break
	if safe:
		print('SAFE')
	else:
		print('UNSAFE')