(False) faces

회사에서 새로 개발한 얼굴 인식 솔루션을 시험하고 있다. 이 프로그램은 인물의 프로필 사진을 보고 그 사람이 누구인지 인식해야 한다. 제대로 동작하는지 확인하기 위해 여러 개의 테스트가 주어진다. 각 테스트에는 $n$명의 인물에 대한 $2n$장의 사진이 들어 있으며, 한 테스트 안에서 각 인물마다 왼쪽 옆모습 사진 한 장과 오른쪽 옆모습 사진 한 장이 있다. 프로그램은 왼쪽 옆모습과 오른쪽 옆모습을 짝지어 주지만 아직 완벽하지 않아서, 때때로 하나의 왼쪽 옆모습에 여러 개의 오른쪽 옆모습이 연결되기도 하고 그 반대의 경우도 생긴다.

일관된 복원(consistent reconstruction) 이란, 모든 왼쪽 옆모습에 서로 다른 오른쪽 옆모습을 하나씩 배정하되 배정된 모든 쌍이 프로그램이 제시한 연결이 되도록 하는 배정을 말한다.

프로그램의 출력(왼쪽)과 가능한 네 가지 일관된 복원.

프로그램을 검사하려면 가능한 모든 일관된 복원을 하나하나 확인해야 한다. 이 확인 작업은 사람이 해야 하며, 회사에는 얼굴 인식에 평생을 바친 네 명의 전문가로 이루어진 팀이 있다. 이들은 한 가지 조건을 걸고 작업을 맡겠다고 한다. 각자의 몫이 똑같아야 한다는 것, 즉 일관된 복원의 개수가 $4$로 나누어떨어져야 한다는 것이다. 당신이 할 일은 그러한지 아닌지를 판정하는 것이다.

입력은 여러 개의 테스트로 이루어진다. 입력의 첫 줄에는 테스트의 개수를 나타내는 양의 정수 $Z \le 100$ 이 주어진다. 이어서 $Z$개의 테스트가 주어진다.

각 테스트의 첫 줄에는 인물의 수 $n$ ($1 \le n \le 300$) 이 주어진다. 그다음 $n$개의 줄이 이어지며, 각 줄은 $0$ 또는 $1$로 이루어진 $n$개의 문자를 담고 있다. $i$번째 줄의 $j$번째 문자가 $1$인 것은 프로그램이 $i$번째 왼쪽 옆모습을 $j$번째 오른쪽 옆모습과 짝지었다는 뜻이며, 그때에만 $1$이다.

각 테스트마다 한 줄씩 출력한다. 프로그램의 연결과 일관된 복원의 개수가 $4$로 나누어떨어지면 YES를, 그렇지 않으면 NO를 출력한다.