Chess Puzzle

Interview

Time limit1sMemory limit128 MB

Summary

For each board, read the rook coordinates and report SAFE if no two rooks share a row or column, otherwise NOT SAFE.

Level: Easy2 of 10
Topics: Implementation, Hash map, Brute force, Array
Solved: No attempts yet

Problem

You want to place several rooks on a chessboard. A rook moves along its own row and column, so for no two rooks to threaten each other, no two rooks may share the same row or the same column.

Given a placement of rooks, write a program that determines whether any rook threatens another.

Input

The chessboard is an $8 \times 8$ board whose squares range from $(1,1)$ to $(8,8)$ .

The first line contains the number of chessboards $T$ .

Each of the following lines describes one chessboard. Each line starts with the number of rooks $k$ , followed by the column and row of each rook in order. In other words, each line contains $k$ pairs of (column, row), that is $2k$ integers.

Output

For each chessboard, print SAFE if no rook threatens another, or NOT SAFE otherwise, on its own line.

Examples3

Example 1

Input

2
3 1 1 2 6 8 8
2 2 3 1 3

Expected output

SAFE
NOT SAFE

Example 2
Input
```
1
1 4 4
```
Expected output
```
SAFE
```
Example 3
Input
```
1
2 5 1 5 8
```
Expected output
```
NOT SAFE
```