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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'res = []\nfor _ in range(int(input())):\n lst = []\n flag = 0\n n = int(input())\n for i in range(n):\n  lst.append(list(map(int, input().split())))\n for i in lst:\n  for j in range(n-1):\n   if i[j] == i[j+1] == 1:\n    res.append("UNSAFE")\n    flag = 1\n    break\n  if flag != 0:\n   break\n for i in range(n-1):\n  for j in range(n):\n   if lst[i][j] == lst[i+1] == 1:\n    res.append("UNSAFE")\n    flag = 1\n    break\n  if flag != 0:\n   break\n if flag == 0:\n  res.append("SAFE")\nfor i in res:\n print(i)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13555