룩

$n \times n$ 크기의 정사각형 판이 있고, 그중 일부 칸은 제거되어 있다. 남아 있는 칸 위에 $n$개의 룩을 다음 규칙을 모두 지키도록 놓으려고 한다.

• 룩은 제거되지 않은 칸에만 놓을 수 있다.
• 한 칸에는 룩을 최대 한 개까지만 놓을 수 있다.
• 어떤 두 룩도 서로 공격하지 않는다. 즉, 모든 행과 모든 열에 룩이 정확히 한 개씩 놓인다.

가능한 배치의 수는 매우 많을 수 있다. 예를 들어 제거된 칸이 하나도 없다면 룩을 놓는 방법은 $n!$가지이다. 당신이 할 일은 이보다 간단하다. 가능한 배치의 수가 짝수인지 홀수인지만 판정하면 된다.

판의 정보를 읽어, 룩을 놓는 경우의 수가 짝수이면 $0$을, 홀수이면 $1$을 출력하는 프로그램을 작성하라.

첫째 줄에 판의 개수 $t$가 주어진다 ($1 \le t \le 10$). 이어서 $t$개의 판 정보가 차례로 주어진다.

각 판 정보의 첫째 줄에는 판의 크기 $n$이 주어진다 ($1 \le n \le 250$). 다음 $n$개의 줄에는 판의 각 행이 순서대로 주어진다. 각 줄에는 $\{0, 1\}$에 속하는 $n$개의 정수가 공백 하나로 구분되어 주어지며, $0$은 그 칸이 제거되었음을, $1$은 그 칸에 룩을 놓을 수 있음을 뜻한다.

각 판에 대해 한 줄에 하나씩, 모두 $t$개의 정수를 출력한다. $i$번째 줄에는 $i$번째 판에서 룩을 놓는 경우의 수가 짝수이면 $0$을, 홀수이면 $1$을 출력한다.

위 그림은 크기가 $3 \times 3$인 한 샘플 판에서 가능한 모든 룩 배치를 나타낸 것이다.