체스 퍼즐

체스판 위에 여러 개의 룩(rook)을 놓으려고 합니다. 룩은 자신이 있는 행과 열을 따라 움직이므로, 어떤 두 룩도 서로를 위협하지 않으려면 두 룩이 같은 행이나 같은 열에 있어서는 안 됩니다.

주어진 룩 배치에서 서로를 위협하는 룩이 하나라도 있는지 판정하는 프로그램을 작성하세요.

체스판은 $8 \times 8$ 크기이며, 각 칸의 위치는 $(1,1)$부터 $(8,8)$까지입니다.

첫째 줄에 체스판의 개수 $T$가 주어집니다.

이어지는 각 줄은 하나의 체스판을 나타냅니다. 각 줄은 먼저 룩의 개수 $k$로 시작하고, 그 뒤에 각 룩의 열(column)과 행(row) 위치가 순서대로 주어집니다. 즉 한 줄은 $k$개의 (열, 행) 쌍, 곧 $2k$개의 정수로 이루어집니다.

각 체스판에 대해, 서로를 위협하는 룩이 하나도 없으면 SAFE를, 하나라도 있으면 NOT SAFE를 한 줄에 출력합니다.