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: interview

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")

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)


# cook your dish here
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")

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)


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)


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)


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")

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)


# cook your dish here
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())))
 #    print(matr)
  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")

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)


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")

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)


# cook your dish here
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):
       #print(k,' ',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
       #print(k,' ',j,' ','2')
       break
    elif(k==n-1 and j!=n-1):
     if(li[k][j]==1):
      if(li[k][j+1]==1):
       x=1
       #print(k,' ',j,' ','3')
       break
   if(x==1):
    print('UNSAFE')
    break
  if(x==0):
   print('SAFE')
   
except:
 pass


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())))
 #    print(matr)
  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


# cook your dish here
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")

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)


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')

# cook your dish here
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())))
 # print(mat)
 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 mat[i-1][j] == 1:
    #     safe = False
    #     break
    # if mat[i-1][j] == 1:
    #     safe = False
    #     break
    
  if not safe:
   # print("UNSAFE")
   break
 if safe:
  print("SAFE")
 else:
  print("UNSAFE")